【算法】树（一）：递归的艺术——分解与遍历、两通道与死亡信号

文章信息

• 原文链接：https://jiayq.blog.csdn.net/article/details/166130453
• 发布时间：2026-09-20 14:25:57
• 标签：#Golang, #算法, ##AtomGit「码动四季·开源同行」秋季征稿活动, ##递归, ##回溯

---

【算法】树（一）：递归的艺术——分解与遍历、两通道与死亡信号

摘要

树系列第一篇。从数组和链表转场树，先修课出乎意料地少——因为树的递归和链表的递归是近亲，分解式和 DP 是同一个灵魂 。本篇五题五课：LC104 最大深度 （树形 DP 的入门形态；”哨兵信任”课——设了哨兵却包 if != nil 防御，等于不信任自己的哨兵）；LC226 翻转二叉树 （”分解式 vs 遍历式”的分界课——我嘴选分解式，手却写了遍历式，铁证是递归调用的返回值根本没人接；顺带一次”回避不是解决”的批判：头插法 O(n) 空间绕过了指针操作，诊断出了断链风险然后回避了它）；LC543 直径 （“返回值与答案分离”课——一个返回值扛两种语义的下场是数字指数膨胀到 62；两通道才是标准姿势）；LC110 平衡二叉树 （”-1 死亡信号”课——发现失衡立即短路，信号走返回值向上透传；以及”造好引擎没点火”的 bug 现场）；LC101 对称 （双参递归 + 镜像交叉；一个 left == right 的超集陷阱）。核心心法一句话：问自己”我需要子树递归的结果吗”——需要就分解式（动作在后序），不需要就遍历式（动作看时机） 。

前置阅读：链表（二）：链表上的双指针——变速、异链与定距，和一份路程账本、双指针与滑动窗口（一）：框架总纲——三类问题、一个原理与判决书。配套代码仓库（按题号分目录）：https://github.com/a18792721831/studyleetCode

1. 树的地图：一个定义、两种心法、三个位置

树的一切递归的源头是它的定义本身：

树 = 根节点 + 左子树 + 右子树，而左右子树各自又是一棵树。

定义是递归的，所以处理树的万能姿势永远是”处理根 + 处理两棵子树”。差异只在心法 ：

心法一【分解】：大问题拆成子树的问题，答案自底向上合成
    maxDepth(r) = 1 + max(maxDepth(r.Left), maxDepth(r.Right))
    —— 这就是 DP！树形 DP 的入门形态

心法二【遍历】：递归函数自己不返回答案，在"路过"每个节点时做事
    答案记录在外部变量里（回溯的 path/res 是它的近亲）

遍历心法里”做事的时机”有三个位置：前序 （进节点时，自顶向下传信息）、中序 （左根右——BST 的命根，下一篇）、后序 （离节点时，子树信息已齐，自底向上合成）。

写任何树题前的第一问：我需要子树递归的”结果”吗？ 需要（用返回值组装答案）→ 分解式，动作在后序；不需要（只要走遍每个节点）→ 遍历式，动作看时机。

2. 第一课 LC104：哨兵要敢信

最大深度。[3,9,20,null,null,15,7] → 3。

分解式的裸题，但我在它身上栽的坑值得单开一节——哨兵信任 ：

if root == nil {
	return 0                    // 哨兵：空树深度 0
}
res := 1
if root.Left != nil {           // ← 病灶：nil 孩子已经被哨兵变成 0 了
	res = max(res, maxDepth(root.Left)+1)
}

哨兵的全部意义，就是让”nil 孩子的情况”自动转移正确 ：叶子的 nil 孩子返回 0，0 + 1 = 1 恰好补上那一层。if root.Left != nil 是在替哨兵重做它已经做好的事——设了哨兵却不敢信它 。删掉两个 if：

func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return 1 + max(maxDepth(root.Left), maxDepth(root.Right))
}

max(0, ...) 让 nil 孩子无声地输掉比较。我在双指针系列被哨兵撞过车 （LC3：0 是合法下标），这次是反向的病：哨兵设对了却重复防御 。两个方向合起来是哨兵的完整课：值要选对（不撞合法域），设了要敢信（不重复防御） 。

3. 第二课 LC226：分解 vs 遍历的分界（含一次回避批判）

翻转二叉树。Home 作者 Max Howell 被 Google 拒掉的那道题。

3.1 先批判一次回避

我的第一版是头插法重建：遍历原链，每到一个节点 new 一个新节点头插到新链——功能全对，O(n) 空间，一次指针操作都没碰 。讽刺的是我注释里写着”当 head.next 的指针被移动，就丢失后续的了”——已经精确诊断出了断链风险，然后用 new 新节点回避了它，而不是解决它 。LeetCode 会 accept（只看输出），面试官会追问”能原地吗”——而原地版才是这题的目标。头插法本身是正经技巧，但用它回避指针操作，恐惧还在，只是没面对。

3.2 嘴选分解，手写遍历

第二版我声称用”分解式”，写出来的是：

tmp := root.Left
root.Left = root.Right
root.Right = tmp        // 做事在递归【前】（前序位置）
invertTree(root.Left)   // ← 返回值根本没人接！
invertTree(root.Right)

铁证在此 ：递归调用的返回值没人接收——你在遍历，不在分解。真正的分解式：

left := invertTree(root.Left)     // 拿回翻转好的左子树（子问题的答案）
right := invertTree(root.Right)
root.Left = right                 // 做事在递归【后】（后序位置）：用返回值组装
root.Right = left
return root

判别口诀钉死：看返回值有没有人接 。接了用（组装答案）→ 分解式；没接（只是走下去）→ 遍历式。两种心法都能 AC 这题（”交换”恰好自顶向下也行），但后面大量题只有一种活路——要合成信息（深度/直径/平衡）必须分解式，要在路径上做事（累加/标记/收集）用遍历式 。选错心法，某些题寸步难行。

4. 第三课 LC543：返回值与答案分离

直径：任意两节点最长路径的边数，不一定经过根。

我在它身上撞了树形递归的第一大坑。第一版：

left := diameterOfBinaryTree(root.Left) + 1     // ← 把返回值当【深度】用
right := max(left, diameterOfBinaryTree(root.Right)+1)
return left + right                              // ← 又把返回值当【直径】算

一个返回值扛两种语义 ：父递归拿到的”直径”被 +1 当深度用，本层又把两个”深度”相加当直径返回——每上一层数字翻倍膨胀，实测 [1,2,3,4,5] 输出 62 （期望 3）。递归铁律：返回值必须有且只有一种语义 。

正解是”两通道”：

var ans int
var depth func(r *TreeNode) int
depth = func(r *TreeNode) int {
	if r == nil {
		return 0
	}
	l := depth(r.Left)
	rr := depth(r.Right)
	ans = max(ans, l+rr)     // ① 答案通道：过 r 的直径候选，逐节点更新
	return 1 + max(l, rr)    // ② 返回值通道：深度，交给父节点组装
}
depth(root)
return ans

递归往上交的是”深度”（父节点要用），真正的答案”直径”住全局变量 ——一个函数两件事，两件事各走各的通道。

口径的账也要先钉死（off-by-one 藏在这）：depth 定义为节点数 （nil=0），则过 r 的路径边数 = depth(L) + depth®——左子树最深链有 depth(L) 个节点，从 r 走到链底恰好 depth(L) 条边。拿示例验证：节点 2 → 1+1 = 2（4→2→5 两条边）；节点 1 → 2+1 = 3。没有多出来的 +1，前提是口径从头到尾不换 ——我第一版口径换了三次。

（这题还附赠一次教练翻车实录：我的测试 build 函数用前序 解析层序 数组，把 [1,2,3,4,5] 建成了左斜链——代码输出 4 是对的，我的 want=3 是错的。测试基建自己带 bug 时，答案对也会被判错；工业界的解法是对拍 ——写一个傻但不会错的参照实现随机对跑。）

5. 第四课 LC110：-1 死亡信号

平衡二叉树：每个节点左右子树高度差 ≤ 1。

结构是 543 的孪生（返回高度、逐节点检查），新维度是：发现失衡之后，还值得继续算吗？ ——答案是不值得，整棵树的判决已经定格为 false。用返回值携带死亡信号短路：

func isBalanced(root *TreeNode) bool {
	var depth func(ro *TreeNode) int
	depth = func(ro *TreeNode) int {
		if ro == nil {
			return 0
		}
		left := depth(ro.Left)
		right := depth(ro.Right)
		if left == -1 || right == -1 || !(left-right <= 1 && left-right >= -1) {
			return -1        // 死亡信号：失衡，或子树已死——向上透传，不再计算
		}
		return max(left, right) + 1
	}
	return depth(root) != -1
}

这版的三个坑按出场顺序记录：

坑一：造好引擎没点火。 我一版定义了 depth 闭包，最后直接 return ans——depth(root) 从未被调用，递归整个没跑，任何树都返回 true。Go 编译器不报错（闭包变量未调用合法）。自查口诀：写完递归题，第一眼找入口调用行 ——它是整台机器的开关。

坑二：区间夹逼写成了并集。 left-right <= 1 || left-right >= -1——差 = 5 时 5 >= -1 成立，整体恒真。|x| ≤ 1 的展开是两个不等式同时成立（交集 &&），我写成了并集（

），把”差在 -1~1 之间”变成了”差是任何数”。夹逼 = &&。

坑三：双信号通道冗余。 中间版本我同时用了全局 ans 和 -1 返回值——两个信号干一件事，还要写胶水代码同步（if !ans { return -1 }）。信号通道一条就够 ：这条 -1 单通道版就是 LC124 最大路径和（hard）的骨架，练它等于预习 hard。

6. 第五课 LC101：双参递归与镜像交叉

对称二叉树：检查是否轴对称。

新形态：一次要同时看两个节点 ——单参递归 dfs(r) 走不通（对称的比较对象是”左子树 vs 右子树”），递归函数长成 compare(l, r) 双参：

var compare func(l, r *TreeNode) bool
compare = func(l, r *TreeNode) bool {
	if l == nil && r == nil {
		return true
	}
	if l == nil || r == nil {
		return false
	}
	if l.Val != r.Val {
		return false
	}
	return compare(l.Left, r.Right) && compare(l.Right, r.Left)   // ★ 交叉
}
return compare(root.Left, root.Right)

★ 行是这题的灵魂：镜像比较是交叉的 ——照镜子时你的左手对应镜中人的右手，所以 l.Left 配 r.Right、l.Right 配 l.Left……笔误自查：写成平行（Left 配 Left）就变成了”两棵子树是否全等”，单侧树会误判。

双参的哨兵从”一个节点”变成”一对节点 “的组合判定——先画全四象限（都空/左空/右空/都非空）再动手，是双参递归的固定起手式。

这题还埋着一个”超集陷阱”值得记：我写了 if left == right { return true }——指针相等 。它覆盖”都为 nil”（我要的）和”同一个节点”（我不想的，只是这题的调用链不会产生）。碰巧安全的代码，复用到别处就是雷——判定写你要的语义，不要写一个超集然后靠调用链的隐含事实兜底 （和 LC167 用 Val 比较代替指针比较是同一课）。

7. 速查表

问题	判据/口诀	出处
选心法	需要子树递归的结果吗？→ 需要分解式（动作在后序）/ 不需要遍历式（看时机）；铁证：返回值有没有人接	LC226
哨兵	值选对（不撞合法域）+ 设了要敢信 （nil→0 之上不再包 if != nil）	LC104
返回值语义	有且只有一种；一值两义 = 指数膨胀（62 之鉴）	LC543
答案放哪	返回值与答案分离：返回值服务父节点组装，答案住全局（两通道）	LC543
口径	depth 定义为节点数（nil=0）；直径候选 = depth(L)+depth®，无 +1；口径全程不换	LC543
提前死亡	-1 哨兵短路（高度域里 -1 非法）；信号通道一条就够	LC110
递归题自查	第一眼找入口调用行（引擎点火）	LC110
区间展开		x	≤ 1 ⟺ x ≤ 1 & & x ≥ -1——夹逼是交集	LC110
双参递归	四象限先画全（都空/一空/一空/都非空）；镜像比较交叉 （l.Left 配 r.Right）	LC101
判定语义	写你要的，不写超集靠运气（指针相等 ≠ 都为 nil）	LC101

总结

五题五课，树形递归的核心武器库齐了。三个层次的收获：

先修课比想象中少。 分解式就是 DP（maxDepth 是树形的打家劫舍）、遍历式就是回溯（外部变量收集）——两个心法都早有肌肉记忆，换的只是树皮。真正新的只有”树的递归定义”这一个出发点。

返回值是树形递归的第一命门。 语义唯一（543 的 62）、两通道分离（答案住全局）、信号短路（-1 透传）——三课其实是同一件事的三个侧面：递归函数是一份契约，返回值是契约的全部条款，调用者怎么解释它必须严格对齐 。

“回避”和”误解”都会写进代码。 头插法回避指针操作（功能对、考点空）、嘴选分解手写遍历（心法标签贴错）——代码不会说谎，它会把你没想清楚的部分原样暴露出来。所以判据永远不是”跑起来对不对”，而是”每个部分你能不能讲出为什么”。

下一篇：BFS 的队列骨架与三配件（102/199/103/107），和这个系列目前为止思维强度最高的 Boss——LC236 最近公共祖先（短路、透传、合流，与返回值语义的升维）。

参考资料

• LeetCode 104. 二叉树的最大深度
• LeetCode 226. 翻转二叉树
• LeetCode 543. 二叉树的直径
• LeetCode 110. 平衡二叉树
• LeetCode 101. 对称二叉树
• 链表（二）：链表上的双指针——变速、异链与定距，和一份路程账本

---

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。