二叉树节点类定义为：class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val; self.left = left; self.right = right；val常用int或None，left/right默认None，不设空列表等非法默认值。
怎么定义二叉树节点类（Python）
二叉树不是 Python 内置类型，必须自己写 TreeNode 类。核心就三点：值、左子节点、右子节点——其他都是干扰项。
常见错误是把 left 或 right 默认设成 []、{} 或空字符串，这会导致后续判断逻辑混乱，比如 if node.left: 在 left 是空列表时也成立，但空列表不是合法子树。
-
val通常用int或None，不建议用默认值掩盖缺失 -
left和right默认为None，这是最安全的初始状态 - 别加多余属性（如
parent、height），除非真需要；加了就得同步维护，容易出错
示例：
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right前序/中序/后序遍历递归怎么写（无返回值版）
三者结构几乎一样，只差一行打印或处理的位置。关键不是记顺序，而是理解“当前节点该在什么时候被访问”。
立即学习“Python免费学习笔记（深入）”；
容易踩的坑是递归终止条件写成 if not node.val:——节点值可以是 0、False、""，但节点本身非空；正确写法永远是 if not node:。
- 前序：先处理
node.val，再递归node.left，最后node.right - 中序：先递归
node.left，再处理node.val，最后node.right - 后序：先递归
node.left和node.right，最后处理node.val
示例（中序）：
def inorder(root):
if not root: # ← 终止条件只看节点是否存在
return
inorder(root.left)
print(root.val) # ← 这里是中序的“中间”
inorder(root.right)返回遍历结果列表时要注意什么
如果函数要返回 list（比如力扣题型），不能在每次递归里新建列表再拼接，否则时间复杂度会退化到 O(n²)。
更常见的错误是写成 return [root.val] + inorder(root.left) + inorder(root.right)——这会产生大量中间列表对象，小树看不出问题，树深一点就明显卡顿。
- 推荐用一个外部列表（如
res = []）传入递归函数，所有节点追加进去 - 或者用生成器（
yield），适合大数场景，但调用方得用list()包一层 - 别依赖
__add__拼列表，Python 列表的+是拷贝操作
示例（前序，返回 list）：
def preorder_list(root):
res = []
def dfs(node):
if not node:
return
res.append(node.val)
dfs(node.left)
dfs(node.right)
dfs(root)
return res为什么递归深度可能出问题
Python 默认递归限制约 1000 层，而链状二叉树（退化成单链）轻松突破这个数，一跑就报 RecursionError: maximum recursion depth exceeded。
这不是算法错，是 Python 的保护机制。本地调试时有人会调高 sys.setrecursionlimit(10000)，但这只是掩耳盗铃——真正上线或数据更大时还会崩，且可能引发栈溢出或内存耗尽。
- 平衡树（如 AVL、红黑树）一般不会触发此问题
- 但输入不可控时（如用户上传序列建树），必须考虑迭代实现或尾递归优化（Python 不支持尾递归，所以实际只能换迭代）
- 面试或刷题中若明确说“用递归”，可先写递归，但最好口头提一句：“生产环境会改用栈模拟递归”
这事没捷径，树深超过几百就得警惕。
