从递归遍历到中档题之间其实隔着一道很多人没意识到的坎递归返回值到底该设计成什么。我见过不少朋友二叉树的前序、中序、层序遍历写得飞起但一碰到需要子树信息向上汇总的题就卡住——要么在递归里搞出双重计算要么返回值定义了却不知道怎么用。这篇文章是“二叉树”系列的第三篇不讲那些入门的遍历和基础属性专门挑几个从“会做简单题”到“能搞定难题”之间的关键能力来讲递归返回值设计、二叉搜索树的删除逻辑、Morris遍历、最近公共祖先、序列化反序列化以及树上DP的基本套路。内容适合学完二叉树基础、想系统性提升的人也适合准备技术面试但总在中档题翻车的同学。我会把每个知识点的原理、代码、容易踩的坑都讲透尽量让你看完就能直接上手用。1. 先把二叉树玩明白的前提递归思维与返回值设计二叉树这棵树之所以看起来简单是因为它有一种自相似的特性每一个节点的左右子树本质上也是一棵二叉树。这个结构决定了递归是处理二叉树最自然的方式但很多人的递归只是“照着模板写”没有真正理解递归函数是在干什么。1.1 自顶向下与自底向上两种完全不同的思考模型处理二叉树的问题你先要问自己一个问题答案是从上往下传还是从下往上汇总自顶向下的模型典型场景是“找从根到叶子的所有路径”“判断是否存在一条路径的和等于目标值”。这种题会把当前路径的状态比如累加和、路径列表作为递归参数往下传到达叶子节点时判断答案。自底向上的模型典型场景是“求树的深度”“判断是否平衡”“树的直径”。这种题要从左右子树分别拿到它们的信息在根节点汇总然后向上返回。这两种模型容易混尤其自顶向下写多了之后看到什么问题都想往下传参数。我自己的经验是如果一个问题需要“子树内部”的信息才能计算答案大概率是自底向上如果答案是沿着路径从头到尾累积出来的大概率是自顶向下。这句话基本能覆盖绝大多数二叉树题。1.2 递归返回值你究竟想向上返回什么自底向上的问题核心就一个字返回值。很多人代码写不出来不是递归逻辑不会而是不知道这个递归函数返回什么、返回的信息够不够用。拿“判断平衡二叉树”来说。一棵树是平衡的需要两个条件左子树平衡、右子树平衡且左右子树高度差不超过1。那递归函数返回什么你当然可以返回布尔值但布尔值里不包含高度信息父节点拿到“True”之后没法算高度差。所以这个递归函数必须返回“高度”这种携带更多信息的类型平衡状态用特殊约定来表示。def is_balanced(root): def dfs(node): # 返回 -1 表示不平衡否则返回子树高度 if not node: return 0 left_h dfs(node.left) if left_h -1: return -1 right_h dfs(node.right) if right_h -1: return -1 if abs(left_h - right_h) 1: return -1 return max(left_h, right_h) 1 return dfs(root) ! -1这里的设计亮点在于用单个值携带两种语义非负数表示子树有效高度-1表示不平衡。这样父节点只要判断返回值是否为-1就能知道自己该返回-1还是继续向上传递合法高度。代码很紧凑但第一次理解的人可能觉得有点绕。介意“魔法数字-1”的话可以用一个类或者元组返回(高度, 是否平衡)两个字段逻辑更直白代价是多写一点代码。实际工程里我倾向于用带字段的小结构但写算法题时用哨兵值往往最方便。1.3 “最大值”类问题的返回值陷阱最大路径和的例子再进阶一步看“二叉树中的最大路径和”这道典型的自底向上题。路径可以从任意节点出发走到任意节点不要求经过根节点。每个节点需要知道两件事经过这个节点的最大路径和是多少更新全局答案以及这个节点能向上贡献的“单臂最大值”是多少返回给父节点。单臂最大值就是从当前节点出发只沿着一条左孩子或右孩子的方向往下走所能取得的最大节点值之和。这个值可能为负数而负数对父节点没有任何贡献所以向上返回时和0取max。def max_path_sum(root): ans float(-inf) def dfs(node): nonlocal ans if not node: return 0 left_gain max(dfs(node.left), 0) right_gain max(dfs(node.right), 0) # 经过当前节点的最大路径 cur_path node.val left_gain right_gain ans max(ans, cur_path) # 向上贡献的单臂值 return node.val max(left_gain, right_gain) dfs(root) return ans注意left_gain max(dfs(node.left), 0)这一步。如果左子树贡献为负宁可把它砍掉路径不从左子树走。这是很多人在实现时容易犹豫的地方明明子树存在为什么返回值可以是0因为路径可以选择不经过任何一侧直接孤零零一个节点也算合法路径。这一章想表达的核心就两句话定义好返回值是第一步返回值的含义要在整棵树上保持一致能用单个值表达的状态不要用两个但状态不够用的时候也别硬塞。2. 二叉搜索树有序序列的树形表达从查找到删除的边界二叉搜索树BST是二叉树中自带排序属性的变种对于每个节点左子树所有节点的值都小于它右子树所有节点的值都大于它。这个结构让查找、插入、删除在平均情况下都能做到 O(log n)但要注意这是“平均”——如果树退化成一串复杂度就跌到 O(n)。2.1 查找和插入递归往下钻直到位置明确BST的查找特别直观小往左走大往右走相等就命中。插入也同理沿着路径找到空位挂上去就行。def insert(root, val): if not root: return TreeNode(val) if val root.val: root.left insert(root.left, val) elif val root.val: root.right insert(root.right, val) # 相等时根据需求处理这里选择忽略 return root这段代码的返回值设计也很典型insert返回“插入完成后的这棵子树的新根”。因为插入操作可能让空节点变成一个有值的节点父节点要重新挂接它的左孩子或右孩子。如果你只传一个引用进去改而不返回就会出现“新节点没挂到树上”的问题。2.2 删除操作三个分支每个分支都有坑删除是BST里最讲究的操作。一共三种情况待删节点没有左孩子直接用右孩子顶替。待删节点没有右孩子直接用左孩子顶替。待删节点两个孩子都在需要用右子树的最小节点或左子树的最大节点来替换它然后再删掉那个被替换的节点。前两种情况好理解第三种为什么不能直接用左或右孩子顶替因为如果直接顶替被顶替的那一侧子树里依然有值大于或小于当前节点的节点会破坏BST的有序性。所以要用“中序后继”来替换右子树里的最小值它比当前节点大但比右子树所有其他节点小替换之后原来的右子树依然满足BST性质。def delete_node(root, key): if not root: return None if key root.val: root.left delete_node(root.left, key) elif key root.val: root.right delete_node(root.right, key) else: # 情况1和2合并 if not root.left: return root.right if not root.right: return root.left # 情况3找右子树最小节点 successor root.right while successor.left: successor successor.left root.val successor.val # 注意递归删除那个后继节点 root.right delete_node(root.right, successor.val) return root容易踩的坑有两个。第一个找到后继之后直接把root.right指向successor.right结果漏删了后继节点。正确做法是递归调用delete_node(root.right, successor.val)让删除逻辑自己处理它。第二递归删除后继时如果后继恰好是root.right本身也就是说右子树没有左孩子这时递归调用会把root.right置为successor.right这没有问题但你要意识到这里发生了“树的局部换根”。2.3 中序遍历有序性判断合法BST不能只比左右孩子BST一个最重要的性质是中序遍历的结果是严格递增的。反过来说一棵二叉树是不是合法BST看它的中序遍历是否严格递增就行。但很多人第一反应是递归判断node.left.val node.val node.right.val这不够。一个反例根节点值是10右孩子是12右孩子的左孩子是9。每个节点和它的直接孩子都满足大小关系但整棵树不是BST因为9出现在10的右子树里却小于10。正确的写法一是用区间def is_valid_bst(root): def dfs(node, low, high): if not node: return True if not (low node.val high): return False return dfs(node.left, low, node.val) and dfs(node.right, node.val, high) return dfs(root, float(-inf), float(inf))写法二是维护中序遍历的前驱节点def is_valid_bst(root): pre None def dfs(node): nonlocal pre if not node: return True if not dfs(node.left): return False if pre is not None and pre.val node.val: return False pre node return dfs(node.right) return dfs(root)我个人偏好第二种因为它顺带锻炼“中序遍历过程中维护状态”的能力。这个能力在查询BST第K小元素时同样有用。3. Morris遍历把空间复杂度压到O(1)的奇技淫巧常规的递归和显式栈遍历栈空间的复杂度是O(h)h是树高。最坏情况下树退化成链h等于n也就是O(n)。有没有可能只用常数空间完成整棵树的遍历有这就是Morris遍历。它的核心思想是利用叶子的空指针做线索thread在遍历过程中临时改造树走完再把树恢复原状。3.1 线索化的核心左子树最右节点的空指针特别强调Morris遍历会临时修改树的结构如果你在并发环境或者遍历过程中不允许改树那就别用。它的代码初看容易绕晕但抓住一条主线就好当指针走到某个节点时先看它的左子树存不存在。如果存在就找到左子树中最右边的那个节点把它的右指针临时指向当前节点——这就是“线索”。有了这条线索当左子树遍历完就能沿线索回到当前节点继续走右子树。以中序遍历为例def inorder_morris(root): cur root while cur: if cur.left is None: print(cur.val) cur cur.right else: # 找左子树的最右节点即中序前驱 pre cur.left while pre.right and pre.right is not cur: pre pre.right if pre.right is None: # 建立线索然后继续深入左子树 pre.right cur cur cur.left else: # 线索已存在说明左子树已遍历完断开线索并访问当前节点 pre.right None print(cur.val) cur cur.right第一次看这段代码最容易懵的是那个while pre.right and pre.right is not cur。这其实是在做两件事如果前驱节点的右指针为空说明这是第一次到达当前节点要建立线索如果右指针已经指向cur说明之前建好的线索还在左子树已经全部走完该断掉线索进入右子树了。判断条件里的pre.right is not cur就是为了防止沿着自己建的线索死循环。3.2 前序遍历的Morris写法区别前序遍历和中序的区别只在一行第一次发现左子树时就立刻访问当前节点。因为前序遍历的顺序是“根、左、右”线索还没建好的时候根节点就要先输出中序遍历则要等左子树全部走完沿线索回来才输出根节点。def preorder_morris(root): cur root while cur: if cur.left is None: print(cur.val) cur cur.right else: pre cur.left while pre.right and pre.right is not cur: pre pre.right if pre.right is None: print(cur.val) # 前序在建立线索时输出 pre.right cur cur cur.left else: pre.right None cur cur.right # 左子树完成右转理解这段代码后你会发现Morris遍历最核心的机制其实就是一个“前驱指针”的临时使用。它把本来需要栈来记录的“回溯路径”藏在了左子树最右节点的空指针里。因此空间只用了两个指针变量O(1)。3.3 为什么后序遍历更麻烦实践里怎么取舍Morris后序遍历要实现“逆序打印”的效果需要在节点从左子树回来时把它左子树的最右路径倒序输出还需要临时反转链表之类的操作。代码复杂度提升不少实际工程中很少有人写。我的建议是把Morris中序遍历和前序遍历理解到位就行这两个能覆盖大部分需要“省空间”的题目。如果面试里真考到后序Morris主动说明它的实现成本高、容易出错通常对方也不会强求。大多数实际系统里树的高度远小于节点数递归或栈的O(h)空间完全够用Morris的亮点更多在于“常数空间”这个极端场景和思维上的启发。还有一件重要的事Morris遍历过程中改变了树的临时结构如果有人在你遍历中途也访问这棵树会看到奇怪的形状。在线环境里的对象锁、任务调度、日志系统如果依赖树的原本结构千万慎用。4. 最近公共祖先、路径收集与序列化三类高频“骨架题”这几类题在二叉树系列里出现频率极高且它们的解决方案可以互相组合。很多看似复杂的题拆开之后都是这几块积木的排列组合。4.1 LCA递归函数一分为二左右都找到才算数最近公共祖先LCA问题是经典的递归设计案例。给定两个节点p和q找到它们往上离得最近的公共祖先。递归思路很简洁在某个节点如果p在它的左子树里找到返回“p所在的那侧结果”如果q在右子树里找到返回“q所在的那侧结果”如果左右两棵子树分别找到了p和q那这个节点就是LCA。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: return root return left if left else right这个写法有个隐含前提p和q都一定存在于树中。如果p存在、q不存在递归返回的结果会是p的某个位置而不是真正意义上的LCA需要额外处理比如先遍历一遍确认两个节点都在。递归在自底向上回溯时左右子树的结果相当于一场“情报汇报”左子树说“我这边找到了p”右子树说“我这边找到了q”当前节点一听自己就是那个汇合点。如果只有一边有情报就把情报原样往上交如果两边都没情报返回None。4.2 路径问题统一框架dfs(path) 状态下沉从根到叶、从根到任意节点、找所有路径等问题共用一套递归模板。核心是把“当前已走过的节点”作为参数往下传叶子节点或满足条件时收集答案。def root_to_leaf_paths(root): res [] def dfs(node, path): if not node: return new_path path [node.val] if not node.left and not node.right: res.append(new_path[:]) return dfs(node.left, new_path) dfs(node.right, new_path) dfs(root, []) return res注意这里我用了new_path path [node.val]而不是path.append(node.val)。因为路径列表在递归中是共享的如果原地修改右子树的递归就会看到左子树已经改过的路径导致结果错乱。用新列表或传入前拷贝能省掉手动回溯path.pop()的麻烦。当然讲究内存效率时用同一个列表回溯更好做算法题时新列表更不容易出错。如果要找“是否存在路径和为 target”不需要收集所有路径可以在进入节点时累加target叶子判断是否等0即可同样适用这个框架。4.3 序列化与反序列化让二叉树跨环境传输二叉树的序列化常见两种做法前序遍历补空标记或者层序遍历补空标记。我喜欢用前序因为它和递归的配合最自然。def serialize(root): res [] def dfs(node): if not node: res.append(#) return res.append(str(node.val)) dfs(node.left) dfs(node.right) dfs(root) return ,.join(res)反序列化时用一个索引指针依次消费序列字符串。遇到#就返回None遇到数字就创建节点然后递归构建左右子树。因为序列化时已经保留了完整的空节点信息所以不需要额外提供中序序列就能唯一重建这棵树。def deserialize(data): vals data.split(,) idx 0 def build(): nonlocal idx v vals[idx] idx 1 if v #: return None node TreeNode(int(v)) node.left build() node.right build() return node return build()这里容易踩的坑是如果用层序遍历序列化反序列化要用队列一层一层建不要试图用数组下标硬算如果用前序序列化递归顺序必须和序列化时的顺序完全一致。我见过不少同学把反序列化的递归顺序写成“先右后左”结果树形状直接错乱排查半天才发现是顺序问题。5. 树上DP一类被低估的套路——子树信息合并“树上DP”听起来高大上其实本质就是自底向上的递归返回值扩展普通递归返回一个值树上DP返回一组状态值然后在父节点做合并。很多同学觉得难是因为之前习惯了递归只返回“树高”“布尔值”这类单一信息突然要返回多个状态就不知道从何下手。5.1 打家劫舍三不选与选两个状态互相制约一个很典型的例子一棵二叉树每个节点有价值不能同时选择相邻节点父子关系算相邻问能偷到的最大价值。对任意一个节点只有两种状态不选它或选它。因此递归函数返回一个包含两个元素的元组(不选时的最大收益, 选时的最大收益)。不选当前节点左右孩子可以随便选或不选所以收益是max(left) max(right)。选当前节点两个孩子都不能选所以收益是node.val left[0] right[0]。def rob(root): def dfs(node): if not node: return (0, 0) left dfs(node.left) right dfs(node.right) not_take max(left) max(right) take node.val left[0] right[0] return (not_take, take) return max(dfs(root))这段代码短但信息量很大。它演示了“状态定义”在树上递归中如何自然展开每个节点不再只是一棵树的高度或布尔值而是携带了一个小决策表。5.2 状态合并时的信息冗余问题有些同学自己写树上DP时会在父节点里重复递归调用同一个子节点好几次比如left dfs(node.left) right dfs(node.right)这是正确做法。但有的人写成max(dfs(node.left)) max(dfs(node.left))这种形式一次递归调用在另一个max里重复执行导致指数级复杂度。如果树有1000个节点原来O(n)的题能跑成天文数字。正确做法一定是先一次递归调用拿到子树返回状态保存在局部变量里再在上层做合并计算。看到这里如果你发现自己写过类似重复递归的代码回头改成保存局部变量性能差距会立刻体现出来。5.3 树的直径左右深度拼起来的经典应用另一个非常适合展示“返回值多语义”的题目是求树的直径任意两个节点之间路径上边的最大数量。计算思路对每个节点经过它的“最长路径”长度等于左子树深度加右子树深度如果某一侧为空就算0。DFS过程中维护一个全局最大值同时向上返回当前子树深度。def diameter_of_tree(root): ans 0 def dfs(node): nonlocal ans if not node: return 0 left_depth dfs(node.left) right_depth dfs(node.right) ans max(ans, left_depth right_depth) return max(left_depth, right_depth) 1 dfs(root) return ans这个题和“最大路径和”异曲同工都需要一个“跨当前节点的临时答案”和一个“向上贡献的单侧值”。把这两个值分开想清楚树上DP的大多数题目就迎刃而解。6. 实操中我反复踩过的几个坑和一些保命技巧写二叉树代码这几年有几类问题我是真的踩过不止一次每次排查都花不少时间。随手记录下来希望对正在写代码的你也有帮助。6.1 递归深度超限不是树的错是语言默认限制的锅在Python环境写递归默认递归深度限制是1000层左右。如果一个测试用例构造出一棵深度几千的链状树你的递归代码会直接抛异常尤其是常规OJ上容易遇到。低阶操作是sys.setrecursionlimit(10**6)能缓解但治标不治本。真正深度大时要么改成迭代式遍历要么改用Morris要么用显式栈模拟递归。我在实际处理极深树时更倾向先评估递归深度会不会成为瓶颈而不是无脑调高限制。6.2 空节点的表示方法别和有效值撞车序列化、路径收集、先序构建树的代码里经常需要一个特殊值来表示空节点。很多人习惯用0但节点值可以是负数也可以是00会和真实节点值冲突。保险做法是用不可能出现在题目数据里的特殊字符串或常量。比如序列化字符串里用#反序列化时遇到#就创建空节点。如果你用整数哨兵一定要确认取值范围不重叠。否则会写出“明明节点是空却把它当成了有值节点”的诡异bug。6.3 Morris遍历断线索的顺序三次写错Morris中最容易翻车的点就是判断前驱节点右指针为空时建线索判断右指针已经指向当前节点时说明左子树已完成必须先断掉线索再访问并转向右子树。我一度把断线和输出顺序颠倒结果下一轮循环又沿着旧线索回到同一个节点造成死循环。保命技巧在纸上画一棵三个节点的树根、左孩子、右孩子。手动模拟一遍中序Morris每一轮指针的变化对“线索何时建立、何时断开”会有非常具体的感知。这比背代码有用得多。6.4 调试二叉树的通用工具先打递归进入和离开的点遇到递归结果不对第一反应应该是加打印。在递归函数开头和结尾分别打印能看到每个节点的进入和离开顺序配合缩进层级基本能还原整个递归过程。我通常在调试时写一个小函数def dfs(node, depth0): if not node: print( * depth None) return 0 print( * depth str(node.val) -) ... print( * depth - str(node.val))这个输出比单步调试更直观尤其适合树这种“调用关系呈分支结构”的场景。很久以后我发现二叉树的题做得顺不顺很大程度取决于你脑子里的“递归模型”建得牢不牢。单纯记住某道题的答案没意义因为题目组合几乎是无限的但一旦你想清楚“这个递归函数返回什么、上一层怎么用这个返回值”很多题自己就能推导出来。到现在我写这些代码时第一件事仍然是问自己这一层的信息要向上汇报成什么想清楚了再动手。