🏠 总目录📚 本教程 02 · 树:递归到底在替你保存什么 ← →
📑 本页目录(点开跳转)

02 · 树:递归到底在替你保存什么

代码题 / 02 · 树与递归

递归返回父节点的,到底是哪一个答案?

先用树深度看孩子怎样把结果交回父节点,再区分队列、路径回退和祖先交汇的各题状态。

读完可按原四题代码说出每题保存什么、交回什么,避免把一种递推套到所有树题上。

题 1 的返回值:孩子把深度交回父节点

  1. 空节点返回 0
  2. 叶子收到两个 0,返回 1
  3. 父节点取左右孩子深度的较大值,再加 1 交回上层
只解释原文题 1 的树深度递推 1 + max(left, right);层序、路径和与最近公共祖先各有不同状态与返回语义。有序集合补充也不属于这条递归路径。图不是执行栈或新运行结果。

⏱ 10 分钟 | 深度、层序、路径和、最近公共祖先

🎯 一句话

树题先别问“怎么递归”;先问:一个节点要把什么答案交回给它的父节点?

🔎 可选深入:普通二叉树与有序 set,保证各在哪里?

本页的普通二叉树递归可以计算高度,却不保证搜索树有序或高度受控。来源问“红黑树实现的 set 有哪些操作”,前一部分仍只补有序集合接口的短对照;后一部分另以 Java 21 的 TreeMap / TreeSet 承载关系、不变量与三键插入修复示意解释高度保证。不展开完整红黑树插入、删除算法或逐行 Java 源码课。

以下以 C++17 std::set 的升序整数集合为明确语境。标准约束顺序、键等价和操作复杂度,不强制实现必须采用红黑树;题面未指定语言,不能自动签成某个 Java 类的完整实现。

操作小例含义复杂度口径
查找 find / count找 5 或确认它是否存在按键查找 O(log n)
普通 insert / 按键 erase加入 5;或删除键 5唯一键集合的常见单次操作 O(log n);不推广到批量/区间
lower_bound / upper_bound第一个不小于 / 严格大于给定键O(log n),顺序由比较器定义
begin/end 顺序遍历按有序次序看所有键完整遍历 O(n);不是随机下标访问
// C++17 语义示意;本轮作者未编译
#include <set>
std::set<int> ordered{5, 2, 9};
// 遍历得到 2, 5, 9;重复 insert(5) 不增加元素
// ordered.find(5) 找到 5;find(6) == ordered.end()
// ordered.lower_bound(6) 指向 9;upper_bound(5) 也指向 9
// ordered.erase(5) 按键删除;不支持 ordered[0] 这种下标访问

键的等价由比较器决定:两边都“不小于对方”时算等价,不一定与 == 完全相同。应保持比较规则稳定,不能把键原地改到破坏排序。上面的 O(log n) 先按比较次数理解,若比较一个长字符串本身有成本,也要算进去。Python 的哈希 set 不提供这组有序边界查询,不能拿名字相同当成同一结构。

再限定到 Java 21:OpenJDK jdk-21+35 的 TreeSet 通常以 TreeMap 承载:集合元素作键,用同一个哑元值 PRESENT 占位;TreeMap 负责红黑树的查找与结构维护,范围视图可共享底层映射。键按比较器(或自然顺序)比较,比较为 0 就视作同一键;要符合 Map/Set 的通用契约,还需与 equals 相容。这里的 Java 实现不是上面 std::set 的实现保证。

把缺孩子的位置画成黑色 NIL 叶,红黑不变量包括:根与 NIL 为黑,红节点不能有红孩子,从任一节点到后代 NIL 的各条路径黑节点数相同。仅看依次插入 3, 2, 1 的局部修复:3B ← 2R ← 1R 出现红红相邻;叔节点是黑 NIL,将 2 改黑、3 改红,再围绕 3 右旋,得到根 2B、左右孩子 1R / 3R。中序仍为 1、2、3,所有到 NIL 的路径黑高相同;这只是一次有限轨迹,不是完整插删实现,也不是 Java 实跑。

对数高度来自一般不变量,不是由这三个节点推出:取根到 NIL 的边数为高度 h,黑高 bh 不含根但含 NIL。无红红给出 h ≤ 2bh;黑高每增加一层所需内部节点的最小数满足递推界,从而 n ≥ 2^bh − 1,所以 h ≤ 2log₂(n+1)。普通二叉树没有这组颜色与黑高约束,不能据此保证高度。

依据:C++ 有序关联容器要求;这里只用 C++17 已有操作,不采用滚动草案新增的接口。

🧩 题 1:二叉树的深度

第 01 章的 next 指向下一项。现在每个节点可以有左、右两个链接。要数清从起点到最远末端经过几个节点,遇到分叉时两边都得看。

一棵有四个节点的二叉树 根节点 1 的左孩子是 2,右孩子是 3。2 的左孩子是 4。3 和 4 都没有孩子。 1234
看最长的一条路。左侧 1 → 2 → 4 经过 3 个节点,右侧 1 → 3 经过 2 个节点。节点里的数字只是值。

一棵二叉树(binary tree)的每个节点至多有两个孩子。起点 1 是根(root),3 和 4 是没有孩子的叶子(leaf)。从任意节点出发、只沿孩子链接向下,能得到一棵更小的子树(subtree)。以下代码假定链接无环,而且每个非根节点只有一个父节点。

本题的整树最大深度按节点数计,等于根的子树高度。递归(recursion)让同一函数先求更小的子树。空子树的高度是 0,所以叶子返回 1。非空节点用 1 + max(left, right),left 和 right 是两棵孩子子树的高度。max 留下能走得更远的一边,加 1 把当前节点也算进去。

从两侧末端向上交回高度
当前节点两侧返回值交回父层
叶子 4 或 30、01 + max(0, 0) = 1
节点 21、01 + max(1, 0) = 2
根 12、11 + max(2, 1) = 3
当程序走到 4,谁还在等?
每次调用保存的参数、临时结果和恢复位置构成一个调用帧(call frame)。最后进入的调用先返回,这串尚未结束的调用就是调用栈(call stack)。
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 为根的子树有多高”。父节点完全不需要知道孩子内部怎么数。

代码中的 root 是当前调用负责的子树根,空时直接返回。令 n 为节点总数,h 为这棵树从根到最远叶子的节点数。用 O(…) 描述操作次数或额外记录随规模增大而增长的速度。每个节点处理一次,每个空孩子也只检查一次,时间为 O(n)。非空树同时最多挂起 h 个非空调用,加一个临时的空节点调用,因此辅助空间为 O(h)。若整棵树只向一边延伸,h 就等于 n。

⭐ 尾递归还要看“回来后做什么”。尾位置的递归调用返回后,当前函数不再有计算要完成。这里还要等待子树结果,做 max 和 + 1,所以不是尾递归。树高为 h 时,尚未返回的调用帧随高度增长,调用栈空间为 O(h);空节点基例还会多一层。

⚠️ 深树可改用显式栈配合循环,把待办状态移到数据结构中;遍历栈仍可能需要 O(h) 空间,不能因此说总辅助空间变成 O(1)。

📌 C++ 的尾调用消除依赖编译器、优化选项与调用形式等条件,并非语言保证;此处的 Python 代码不是 C++ 优化演示。CPython 的 tail-call interpreter 也不等于 Python 函数的尾递归优化(依据:GCC 优化说明、CPython 3.14 说明)。

🧩 题 2:从上往下打印二叉树

假如先沿左侧走到底,4 会比 3 更早出现。要让浅层先输出,先把等候处理的节点放进队列(queue),先入队的节点先出来。这个从近到远的过程叫层序遍历,也就是这里的广度优先搜索(Breadth-First Search,BFS)。

沿用题 1 的树。队首在左,输出按时间顺序追加
刚取出孩子入队后已输出
尚未开始[1][]
1[2, 3][1]
2[3, 4][1, 2]
3[4][1, 2, 3]
4[][1, 2, 3, 4]

在代码里,popleft() 取队首,append() 把左孩子、右孩子依次放到队尾。4 排到 3 后面,于是第三层必须等第二层处理完。若在同一端取放,就会先取最后放进去的孩子,输出顺序随之改变。

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]

令 w 为最宽一层的节点数。每个节点入队和出队各一次,时间是 O(n)。队列可能同时保留当前层剩余的节点和下一层已加入的节点,最多 2w 个,辅助空间是 O(w)。返回的输出列表另占 O(n)。空树直接返回 []。

如果先沿一条路走到底

深度优先搜索(Depth-First Search,DFS)沿一条分支深入,再回到之前的分叉。对于同一棵二叉树,约定先处理左子树、再处理右子树。把输出当前节点放在三个不同的位置,就得到三种遍历。

移动的是“记录当前节点”这一步
遍历每层执行顺序图中四个节点的输出
前序(preorder)当前 → 左 → 右1、2、4、3
中序(inorder)左 → 当前 → 右4、2、1、3
后序(postorder)左 → 右 → 当前4、2、3、1

接在题 2 的 Python 示例后运行。沿用同一个 root,output 接收依次记录的节点值。

def inorder(node, output):
    if node is None:
        return
    inorder(node.left, output)
    output.append(node.val)
    inorder(node.right, output)


output = []
inorder(root, output)
assert output == [4, 2, 1, 3]

执行到 4 时,空左子树立即返回,所以先记下 4。回到 2 才记下 2,再回到根记下 1,最后进入右侧记下 3。把 output.append(node.val) 移到两个递归调用之前或之后,就能验证前序和后序。遍历需要 O(n) 时间和 O(h) 调用栈空间,输出列表另计。中序按树的左右结构输出。只有树满足二叉搜索树的顺序约束(左子树的值都小于当前值,右子树的值都大于当前值,以键各不相同为例),才能保证输出从小到大。

🧩 题 3:二叉树中和为某一值的路径

path 记录当前这条根到节点的路。走进一个节点时加入,离开它时弹出。试另一条路之前,先把共享列表恢复到分叉处。

沿用代码里的演示数据,目标和是 22。进入节点时,从还差的数 remain 里减去节点值。只有走到叶子且恰好减到 0,才把完整路径存入答案。

在分叉 11 先试 7,再试 2
动作共享的 path这层的 remain
依次进入 5、4、11[5, 4, 11]22 − 5 − 4 − 11 = 2
试左叶子 7[5, 4, 11, 7]2 − 7 = −5,跳过
弹出 7,回到 11[5, 4, 11]仍是 2
试右叶子 2[5, 4, 11, 2]2 − 2 = 0,保存副本

remain 是每层自己的整数,回到 11 时仍是 2。path 是所有层操作的同一份列表,所以要主动撤销。两边都走完,11 也要从路径里弹出。这样回到根 5 后,右侧可以用干净的 [5] 继续。

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) 是高频错:所有答案都指向同一个会继续变化的列表,最后会一起变空。

空树返回空列表。即使在中途凑齐了目标值,也要走到叶子才可以记答案。把一次整数运算按一步计,遍历本身花 O(n)。令 L 为所有命中路径拷贝的节点值总数,连复制算在内,时间为 O(n + L)。递归和当前路径共需 O(h) 辅助空间,返回的路径另占 O(L)。

🧩 题 4:两个节点的最近公共祖先

两条从根出发的路线可能先共用一段,再分开。最近公共祖先(Lowest Common Ancestor,LCA)是两条路线最后一个共同节点。路线包含目标自己,所以目标也可能是答案。

跟着题 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) 会交回“在这棵子树里找到的目标节点,或已经确定的公共祖先”。

左右都找不到时会返回 None。这里的 a、b 是树里实际存在的节点,is 比较的是节点身份,值相同的两个节点仍能分开。若一个目标缺失,代码可能只交回另一个目标。调用方应先确认两个目标均存在。最坏访问所有节点,时间 O(n),调用栈空间 O(h)。

🔗 这一章连到哪里

去哪 为什么
不靠数据的 AI 06 · 无信息搜索 ⭐ 那一章会把搜索待办显式写出来。DFS 的栈先取最近加入的项,BFS 的队列先取最早加入的项。本章题 2 的层序打印就是树上的 BFS。

本节回顾

树的递归不是魔法:每层只做“处理当前节点 + 向孩子要答案 + 把自己的答案交回去”。

按层找节点时,用队列保存待办。按路径尝试时,记清哪些数据随调用一起返回,哪些共享数据需要撤销。下一章会继续练习栈和队列的出入顺序,第 06 章会把路径回退用到矩阵与排列上。

✅ 检查点

路径和题为什么离开节点时必须 path.pop()?

👀 看答案

因为同一个 path 会被左右子树共用。离开左子树不弹出,右子树会带着一段不属于它的旧路径继续走。

先预测。 把题 1 的四个节点改成一条只向左的链,深度函数最多同时有几层调用?层序队列最多同时有几个节点?

👀 看形状如何改变空间

深度为 4。走到底时 4 个非空调用还未返回,再加检查空孩子的一层,一共 5 层。层序每次取一个,再放入唯一的孩子,队列最多有 1 个节点。两种方法都处理了 4 个节点,峰值所需的工作空间随树形不同。

再判断。 根节点值为 5,唯一的叶子值为 −2。目标是 3,进入根时 remain 已经小于 0。能提前返回吗?

👀 看负数如何改变剩余值

继续走。到根后还差 3 − 5 = −2,到叶子后还差 −2 − (−2) = 0,所以应保存 [5, −2]。如果允许负数,仅凭还差的数小于 0 就结束,会漏掉这条路径。


⚡ 走神救援

继续: 03 · 栈、队列和窗口:谁应该先出来

打卡记录保存在你的浏览器里,首页能看到总进度