📑 本页目录（点开跳转）
02 · 树：递归到底在替你保存什么
⏱ 10 分钟 ｜ 深度、层序、路径和、最近公共祖先
🎯 一句话
树题先别问“怎么递归”；先问：一个节点要把什么答案交回给它的父节点？
🧩 题 1：二叉树的深度
叶子节点的深度是 1；非叶子节点只需拿左右孩子的答案，取较大再加 1。
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def depth(root):
if root is None:
return 0
return 1 + max(depth(root.left), depth(root.right))
root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
assert depth(root) == 3
递归契约：depth(node) 永远返回“以 node 为根的子树有多高”。父节点完全不需要知道孩子内部怎么数。
🧩 题 2：从上往下打印二叉树
这不是递归题，而是“先来的先处理”：用队列做层序遍历。
from collections import deque
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def level_order(root):
if root is None:
return []
queue, answer = deque([root]), []
while queue:
node = queue.popleft()
answer.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return answer
root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
assert level_order(root) == [1, 2, 3, 4]
🧩 题 3：二叉树中和为某一值的路径
关键不是找路径，是回去时清干净。 path 记录当前这条根到节点的路；走进一个节点时加入，离开它时弹出。
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def path_sum(root, target):
answer, path = [], []
def visit(node, remain):
if node is None:
return
path.append(node.val)
remain -= node.val
if node.left is None and node.right is None and remain == 0:
answer.append(path[:]) # 复制当前答案，不能直接塞 path
visit(node.left, remain)
visit(node.right, remain)
path.pop() # 回到父节点前复原现场
visit(root, target)
return answer
root = TreeNode(5, TreeNode(4, TreeNode(11, TreeNode(7), TreeNode(2))), TreeNode(8))
assert path_sum(root, 22) == [[5, 4, 11, 2]]
⚠️ answer.append(path) 是高频错：所有答案都指向同一个会继续变化的列表，最后会一起变空。
🧩 题 4：两个节点的最近公共祖先
若当前节点就是 a 或 b，把自己交回去；左右子树各交回一个目标，当前节点就是交汇点；只交回一边，就把那一边继续交给父节点。
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def lowest_common_ancestor(root, a, b):
if root is None or root is a or root is b:
return root
left = lowest_common_ancestor(root.left, a, b)
right = lowest_common_ancestor(root.right, a, b)
if left and right:
return root
return left or right
n4, n5, n2 = TreeNode(4), TreeNode(5), TreeNode(2)
root = TreeNode(1, n2, TreeNode(3))
n2.left, n2.right = n4, n5
assert lowest_common_ancestor(root, n4, n5) is n2
这题的递归契约更具体：lowest_common_ancestor(node, a, b) 会交回“在这棵子树里找到的目标节点，或已经确定的公共祖先”。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 不靠数据的 AI 06 · 无信息搜索 | ⭐ 递归替你保存的那个栈，那一章把它显式写了出来：DFS 用栈、BFS 用队列，两个算法只差这一行。本章题 2 的层序打印就是那里的 BFS |
🛑 可以停在这里
树的递归不是魔法：每层只做“处理当前节点 + 向孩子要答案 + 把自己的答案交回去”。
✅ 检查点
路径和题为什么离开节点时必须 path.pop()？
👀 看答案
因为同一个 path 会被左右子树共用。离开左子树不弹出，右子树会带着一段不属于它的旧路径继续走。
⚡ 走神救援
- 深度：子树把高度交回来，当前层取最大再加一。
- 层序：队列；先入队的节点先处理。
- 路径：进节点
append，离开节点pop，保存答案用path[:]。 - LCA：左右各找到一个目标时，当前节点就是交汇点。