def traverse(root): if not root: # base case return # 前序位置（刚进入节点时） traverse(root.left) # 中序位置（左子树返回后） traverse(root.right) # 后序位置（右子树返回后）
三个位置的关键区别：
位置
时机
典型应用
前序
刚进入节点，还没处理子树
构造、复制、翻转
中序
左子树处理完，右子树还没处理
BST 相关（有序）
后序
左右子树都处理完
求深度、路径、直径
BFS（层序遍历）
from collections import dequedef level_order(root): if not root: return [] res = [] q = deque([root]) while q: level_size = len(q) level = [] for _ in range(level_size): node = q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) res.append(level) return res
三、核心模板
模板 1：二叉树最大深度（后序 + 分解法）
def max_depth(root): if not root: return 0 left_depth = max_depth(root.left) right_depth = max_depth(root.right) return 1 + max(left_depth, right_depth)
模板 2：翻转二叉树（前序 + 遍历法）
def invert_tree(root): if not root: return None # 前序位置：交换左右子树 root.left, root.right = root.right, root.left invert_tree(root.left) invert_tree(root.right) return root
模板 3：验证 BST（中序 + 全局变量）
def is_valid_bst(root): # 中序遍历 BST 应严格递增 prev = float('-inf') def inorder(node): nonlocal prev if not node: return True if not inorder(node.left): return False if node.val <= prev: return False prev = node.val return inorder(node.right) return inorder(root)
模板 4：最近公共祖先（后序 + 分解法）
def lowest_common_ancestor(root, p, q): if not root or root == p or root == q: return root left = lowest_common_ancestor(root.left, p, q) right = lowest_common_ancestor(root.right, p, q) if left and right: # p 和 q 分别在左右子树 return root return left or right # 返回找到的那一侧