★ FEATURED ARTICLE 1. 从“15二叉树5”这个标题说起我为什么挑这五个考点这个标题看着像一串学习计划的缩写“15二叉树5”。对正在刷题的人来说它大概率指的是二叉树专题的第15次练习或者某个系列里的第5篇讲解。不管编号怎么排落点都是同一个二叉树已经过了“前中后序遍历”“层序遍历”“翻转”这些入门坎该往中阶进阶了。二叉树的进阶方向其实很集中翻来覆去就是几件事状态怎么在递归里向上传递、路径怎么收集、多个节点之间的关系怎么确定、一棵树怎么被“改造”成另一种结构、一棵树怎么被完整地存下来再还原。这五个方向如果只用五道题来代表我会挑对称性判断、路径总和系列、最近公共祖先、二叉树展开为链表、序列化与反序列化。它们正好对应了二叉树递归设计里的五种典型思维模型每一道都能带出一串变形题。这篇记录不是把某一道题的标准答案贴出来就完事。我把自己在练习过程中反复踩过的坑、看别人代码时容易卡住的点以及每个考点背后的“为什么这样做”都写清楚了。代码用的都是最常见的树节点定义和递归套路适合正在从“能看懂”走向“能独立写出来”的读者也适合面试前想快速把二叉树中阶考点过一遍的人。1.1 这五个考点分别考什么先做一张总览表方便往后看的时候随时对照。考点核心能力典型难度面试频率对称性判断递归参数设计、两棵树同时比较中低高路径总和系列递归遍历、回溯收集、前缀思想中很高最近公共祖先自底向上传递信息、后序遍历中高很高二叉树展开为链表原地修改指针、前驱节点中高中序列化与反序列化协议定义、递归构造、工程封装中高中高这类题目在常见的刷题平台、教材和高频面经里出现概率都很高不是从某一道题里抄出来的组合而是二叉树中阶阶段最有代表性的五类问法。1.2 它们之间的递进关系这五个考点不是孤立的安排顺序有讲究。对称性判断是“递归返回值”的入门课它的递归函数一次要比较两个节点很多人在这一步第一次意识到“递归参数可以不止一个”。路径总和系列把递归从“返回一个布尔值”推进到“返回一组路径”顺带把回溯、参数携带累计值这些概念带出来。最近公共祖先又往前走一步要求递归函数在左右子树里分别收集信息最后在当前层做汇总这是自底向上的标准模型。二叉树展开为链表看起来和前三个不一样但它要的是“站在当前节点决定左子树和右子树怎么重新拼接”非常考验对树结构走向的把控。序列化与反序列化则是综合题递归遍历、细节协议、边界情况全都要处理相当于把前面几个考点揉在一起。下面逐个拆开讲。2. 对称性判断递归里最容易写飘的一个点判断一棵二叉树是否关于根节点轴对称题目描述很简短但不少人上手就错。最常见的错误是只拿一个节点递归去比较它的左孩子和右孩子结果逻辑越写越乱。实际上“一棵树对称”应当翻译成“它的左子树和右子树互为镜像”。2.1 递归版把“一棵树对称”翻译成“两棵树互为镜像”镜像关系的定义是两个根节点值相同并且第一棵树的左子树与第二棵树的右子树互为镜像第一棵树的右子树与第二棵树的左子树互为镜像。这里的递归函数天然就需要两个参数分别代表两侧的节点。def is_symmetric(root): if not root: return True return is_mirror(root.left, root.right) def is_mirror(left, right): if not left and not right: return True if not left or not right: return False return (left.val right.val and is_mirror(left.left, right.right) and is_mirror(left.right, right.left))写这个函数时心里要始终明确当前这一步在做什么先判断两个节点存不存在再判断值相不相等最后递归比较“交叉”的两对子树。空节点的处理顺序特别关键必须先写“两个都为空返回True”再写“其中一个为空返回False”这两个条件顺序反了会出现空指针访问。2.2 迭代版用队列保持“镜子配对”递归版足够简洁但为了更直观地理解镜像关系可以用队列把每一层要比较的成对节点放进去。每从队首取出两个节点就像把一面镜子放在中间看两边对应的位置是否一致。from collections import deque def is_symmetric_iter(root): if not root: return True q deque([root.left, root.right]) while q: left q.popleft() right q.popleft() if not left and not right: continue if not left or not right or left.val ! right.val: return False q.append(left.left) q.append(right.right) q.append(left.right) q.append(right.left) return True注意入队顺序必须严格保持配对左节点的左孩子对应右节点的右孩子左节点的右孩子对应右节点的左孩子。队列里始终是两两一组所以每次循环取两个节点。2.3 常见误区与自测用例我犯过的典型错误是只判断了树的一半。比如递归时只比较root.left和自己或者只拿左子树和右子树逐层比较对应位置却忘了“镜像”意味着要交叉比较。自测时可以用这几个案例一棵完全对称的树比如[1,2,2,3,4,4,3]一棵值不对称的树比如[1,2,2,None,3,None,3]还有单节点和空树这两种极端情况。对称性判断的递归模板非常容易迁移。“判断两棵树是否完全相同”只需要把交叉比较改成同向比较“判断一棵树是否包含另一棵树”也建立在完全相同的基础上。所以把这个递归思维吃透后面好多题都能用上。3. 路径总和系列从“有没有”到“所有路径”的递进关系路径总和系列是二叉树递归里最典型的“层层递进”题型。第一问只问有没有第二问要求把所有路径列出来第三问把起点从根节点放宽到任意节点。难度看似线性增加实际上每一步都引入一个新的编程要点。3.1 第一层从根到叶有没有最简单的一版是给定目标和判断从根节点到叶子节点是否存在一条路径使得路径上所有节点值之和等于目标和。实现时不需要真的累加用一个“剩余值”不断做减法更省事。def has_path_sum(root, target_sum): if not root: return False if not root.left and not root.right: return root.val target_sum return (has_path_sum(root.left, target_sum - root.val) or has_path_sum(root.right, target_sum - root.val))叶子节点在这里被明确为“左右孩子都为空的节点”。递归时减去当前节点值到叶子节点时比较剩余值是否等于节点值。这个写法很直观但要注意空树直接返回False不要把空树当成目标值等于0的情况。3.2 第二层把路径全部收集起来第二问变成“找出所有从根到叶且和为目标的路径”。这时不仅要判断还要记录整条路径。关键点有两个路径列表的复制时机以及回溯时的恢复操作。def path_sum_list(root, target_sum): result [] def dfs(node, remaining, path): if not node: return if not node.left and not node.right: if remaining node.val: result.append(path [node.val]) return dfs(node.left, remaining - node.val, path [node.val]) dfs(node.right, remaining - node.val, path [node.val]) dfs(root, target_sum, []) return result这里我用path [node.val]这种方式传递路径每次函数调用都会生成新的列表天然避免了回溯时误删已记录路径的麻烦。如果你习惯用path.append(...)再path.pop()那就要特别注意只有递归返回之后才能pop而且result.append(path[:])必须复制一份否则后面对path的修改会影响已经存入结果的对象。3.3 第三层起点不在根节点第三问是路径不需要从根节点出发也不需要在叶子节点结束节点值可正可负统计路径数量。最朴素的想法是遍历每个节点把每个节点都当作“根”往下找和为目标的路径。def path_sum_any(root, target_sum): if not root: return 0 def count_from(node, remaining): if not node: return 0 count 1 if node.val remaining else 0 count count_from(node.left, remaining - node.val) count count_from(node.right, remaining - node.val) return count return (count_from(root, target_sum) path_sum_any(root.left, target_sum) path_sum_any(root.right, target_sum))这个写法的时间复杂度是O(n^2)面试时如果被追问可以用“前缀和加哈希表”优化到O(n)。“前缀和”在这里指从根到当前节点的累计和哈希表记录某个累计和出现的次数。路径和为target等价于存在某个更早的节点使得“当前累计和 - 早期累计和 target”。不过初学者先把暴力版本写对更重要优化是在思路成熟之后的事。3.4 为什么这三问要连着练因为它们是同一个递归框架下的三层深化第一问只关注返回值第二问加入了路径收集第三问把搜索范围从单条路径扩展到全树。很多人在第二问里出错问题不在递归逻辑而在列表引用和剪枝时机。第三问表面上只是加了一层外层遍历实际上已经把“路径”这个概念从“根到叶”扩展成了“任意连续段”。练这三问还有一个额外收获你会自然而然地分清“递归函数返回值”和“递归过程中的副作用”。第一问靠返回值第二问靠外层结果列表收集第三问两者都要。这个意识对后面的所有树形动态规划题都很重要。4. 最近公共祖先自底向上收集信息的典型套路最近公共祖先大概是二叉树递归里最值得反复琢磨的一道题。它没有一个明显的“自上而下”的计算过程而是依赖递归在返回时把信息一层一层往上带。很多教材和博客把它背成模板但如果不理解“返回值到底代表什么”换一个问法就容易写错。4.1 自底向上后序遍历的精髓定义很简单对于一棵二叉树中的两个节点p和q找到距离它们最近的公共祖先。求解时标准做法是后序遍历也就是先处理左子树再处理右子树最后处理当前节点。为什么是后序因为在当前节点做决策时必须知道左子树和右子树里分别有没有p或q。可以想象成一层办公楼里有两个员工p和q每个节点是一个楼层主管。主管先问左边楼层能不能找到p或q再问右边楼层最后结合两边回报决定自己是不是公共祖先。这个过程必须是“从下往上”的。4.2 代码实现与返回语义def lowest_common_ancestor(root, p, q): if not root or root is p or root is 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。写的时候容易忽略root is p or root is q这个条件少了它递归会在找到p之后继续往下走把已经找到的目标节点弄丢。返回值的语义必须统一返回值要么是空节点表示子树里没有目标要么是非空节点表示子树里找到了p或q或者已经找到了公共祖先。当left和right都不为空时说明p和q分别出现在当前节点的左右子树中当前节点就是公共祖先。4.3 一个容易误判的例子举个例子一棵树是[3,5,1,6,2,0,8]p是值为5的节点q是值为6的节点。注意6是5的左孩子。从根节点3开始后序遍历左子树返回5右子树没有找到q继续往上走根节点发现左右结果中只有左边非空于是返回5。这个结果是正确的因为6本身就是5的后代5就是最近公共祖先。如果终止条件里漏了root is p这条判断过程会变成走到5时没有立即返回而是继续往左找6结果下面的递归可能会返回6最后根节点只会知道右子树没有结果、左子树找到6于是错误地返回6。所以记住当节点正好是p或q时它就是当前子树里已经找到的答案不需要再往下看。这个递归设计思想还能泛化到“求二叉树中两节点之间的路径”“判断一个节点是否在子树中”等题目。核心都是让递归返回值携带足够明确的信息然后在当前层汇总。5. 二叉树展开为链表原地修改的指针操作把一棵二叉树按照前序遍历的顺序展开成一条单链表要求右指针指向下一个节点左指针全部置空并且必须在原树上原地修改。这题光看定义不难真正动手时最容易出问题的地方是把左子树移动到右子树位置之后原来的右子树去哪了5.1 先想最直接的方案前序遍历再串最稳妥的解法是前序遍历一次把节点按顺序存进列表然后遍历列表依次把前一个节点的left置空、right指向下一个节点。空间复杂度O(n)正确性非常容易保证。def flatten_with_list(root): nodes [] def preorder(node): if not node: return nodes.append(node) preorder(node.left) preorder(node.right) preorder(root) for i in range(len(nodes) - 1): nodes[i].left None nodes[i].right nodes[i 1]这个方案在面试里可以作为第一版答案它至少证明你理解前序遍历和链表拼接。但如果面试官追问“能不能别用额外空间”就需要原地算法。5.2 原地修改的标准写法原地算法的核心思路是对于当前节点如果它有左子树就找到左子树里最靠右的节点这个节点是左子树在中序遍历意义上的最后一个节点也是当前节点右子树的前驱。然后把当前节点的右子树接到前驱的右指针上再把整个左子树搬到当前节点的右子树位置左指针置空最后移动当前指针。def flatten(root): cur root while cur: if cur.left: predecessor cur.left while predecessor.right: predecessor predecessor.right predecessor.right cur.right cur.right cur.left cur.left None cur cur.right这段代码里最容易漏掉的是内层循环。它一直往左子树的右边界走走到不能再往右为止。如果没有这一步直接cur.right cur.left会导致原来的右子树彻底丢失。5.3 指来指去最容易失手的地方我最初写这段代码时犯了一个经典错误移动完cur.right之后没有把cur.left置空。这样一来虽然单链表的right链是连上了但原树上还残留着左指针后续循环里cur.left又可能不为空导致Inner循环重复处理同一个子树甚至形成环。另一个容易出问题的点是前驱节点的选择。前驱不是左子树的根而是左子树最右边的节点。如果左子树自身也很大需要沿着right一路走到头。这个“往右走到头”的过程本质上就是在模拟前序遍历中“左子树访问完回到当前节点再走右子树”的衔接点。画图是解决这类指针题最有效的手段。把当前节点标记为A左子树根为B右子树根为C左子树的最右节点为D。原结构的访问顺序是A、B、B的左子树、D、C。展开后希望变成A、B、...、D、C。所以本质上就是把C移动到D的右指针下再把B放到A的右指针下。想清楚这条链路代码就不会写错。6. 二叉树的序列化与反序列化面试里最考验工程感的题目序列化是把一棵二叉树变成长字符串反序列化是把这个字符串还原成结构完全相同的树。看起来只是“存起来再读出来”但它的难点在于树结构里大量空指针需要一种无歧义的表示方式才能保证反序列化结果唯一。6.1 序列化把树变成带占位符的字符串我用前序遍历加空节点占位符的方式来实现。前序遍历的顺序是“根、左、右”每个空节点用字符串None表示节点之间用逗号分隔。序列化的结果形如1,2,None,None,3,4,None,None,5,None,None。def serialize(root): parts [] def dfs(node): if not node: parts.append(None) return parts.append(str(node.val)) dfs(node.left) dfs(node.right) dfs(root) return ,.join(parts)用逗号而不用空格的目的是避免节点值是负数或多位数时产生歧义。比如12和1,2会被错误解读而逗号分隔后每个切片就是一个完整节点值。6.2 反序列化用迭代器吃掉整棵树的骨架递归构造时用一个迭代器持续取出下一个值。遇到None就返回空节点否则创建节点再递归构造左子树和右子树。def deserialize(data): def dfs(it): val next(it) if val None: return None node TreeNode(int(val)) node.left dfs(it) node.right dfs(it) return node return dfs(iter(data.split(,)))这个递归顺序和前序遍历严格对应。序列化时先写根节点反序列化时一定先建根然后填左子树等左子树结束之后迭代器自然指向右子树的位置。只要数据格式约定一致重建过程就不会乱。6.3 为什么前序遍历加None标记就够因为前序遍历携带了充分的“空指针”信息。一个None等价于告诉反序列化器“这个位置没有节点请返回上一层继续”。每个None会消耗掉一次递归调用让迭代器位置正确推进。这里值得理解的一点是只靠前序或中序或后序遍历序列如果没有空指针标记通常无法唯一确定一棵二叉树。加上了None占位后递归序完全确定这棵树就可以被唯一重建。所以序列化协议设计的核心不是“存了哪些值”而是“如何表达空位”。6.4 和BFS序列化的对比前序遍历只是其中一种方式用层序遍历也能做。BFS序列化用队列作为辅助空节点同样写入None反序列化时配合索引重建左右孩子。两种方法复杂度都是O(n)前序写起来更短但递归深度等于树高极端情况下树形非常倾斜时可能压爆栈BFS用迭代方式实现没有递归栈深度问题但要自己控制层与层之间的关系。如果你在实际项目里要用这套逻辑建议把节点分隔符、空节点标记、负数处理都放到一个配置里统一管理。别小看这些细节面试里经常有人因为分隔符选错或者把空节点标记写成了空字符串最后反序列化出来一堆意外结果。7. 复盘笔记五种题型的通用心法五个考点全部过完一遍比起单道题答案更重要的是它们背后反复出现的五件事。这些思维要点不只在二叉树里成立放到多叉树、回溯、图遍历里同样适用。7.1 五道题背后的五条通用心法第一条写递归前先问自己三个问题终止条件是什么、当前层要处理什么、返回值代表什么。对称性判断的返回值是“是否镜像”路径总和的返回值是“是否存在路径”LCA的返回值是“找到的目标或公共祖先”每种函数的返回值语义都不同先想清楚再动手。第二条凡是需要同时比较两棵树的题目就大胆增加递归参数。对称性判断从单节点递归改成双节点递归后思路立刻清晰。很多等价树、包含树问题都可以用同样的方式解。第三条自底向上收集信息时优先考虑后序遍历。LCA问题的核心就是先拿到左右子树的结论再在当前节点汇总。后序不是一种“顺序偏好”而是这类信息流的必然要求。第四条指针修改类题目先画图再写代码。展开为链表的题只要把前驱节点和右子树的迁移关系画清楚代码就是照图说话。第五条序列化类题目先定协议再写实现。分隔符、占位符、值的格式这些都属于协议。协议定了序列化和反序列化就是一对互逆操作。7.2 一页纸的易错点对照清单考点最易出错位置自测重点对称性判断空节点判断顺序、交叉比较方向单节点、左右空、值不对称路径总和系列叶子判断、路径列表复制、回溯恢复负数节点、空树、单左链最近公共祖先root is p or root is q条件遗漏p是q祖先、q在左子树、节点不存在展开为链表左子树置空、前驱选择错误只有左子树、只有右子树、左右都有序列化与反序列化分隔符、None占位、递归顺序负数节点、空树、单节点这张表是我在整体复习阶段反复用的。每次看完一道题不急着做下一题先在纸上把易错点默写一遍然后跑几个边界用例比自己闷头写十道题都管用。7.3 我的练习顺序与复盘习惯个人经验是二叉树专题千万不要按题目难度从低到高硬刷而是按“思维模型”分类刷。对称性、路径总和、LCA、展开、序列化各挑两三道题做完一组立刻总结这个模型在哪几个地方容易卡壳再去做下一组。我习惯每道题写注释时先写清递归函数的返回值语义。比如is_mirror返回“两棵树是否互为镜像”lca返回“当前子树中是否找到p或q如果都找到则返回公共祖先”。把这句话写在函数名下面写主逻辑时脑子不容易乱。另一个习惯是给每道题准备三个测试用例一个正常多岔结构、一个全左链或全右链、一个空树。三个用例跑过大多数常见错误都能暴露出来。二叉树的中阶进阶本质上就是对“递归返回值”和“节点之间关系”的掌控。把这五类考点的思维模型吃透后面再遇到树形动态规划、二叉搜索树进阶、N叉树题目时你会发现很多套路都是相似的。
阅读完成 · 觉得有帮助？
