二叉树相关的算法题我前前后后刷过三轮。第一轮看到递归就想避开第二轮照着模板写能过不少题第三轮才慢慢意识到所谓二叉树算法本质上训练的是两件事——怎么把一个大问题拆成左右两个子问题以及怎么让递归的返回值替你表达结果。这篇汇总不按题号顺序记按思路分类整理把常见考法、核心写法、以及真正容易踩的地方放在一起讲。无论你是刚开始接触树还是准备面试前想系统过一遍这篇文章都适合当一份提纲用。1. 前置认知二叉树的递归其实是“把大问题切成两个小问题”1.1 先吃透节点结构再谈算法二叉树的所有操作都建立在一个极简结构上一个节点有值最多向左走一步向右走一步。用常见的定义写出来是这样class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val val; this.left left; this.right right; } }很多人在刚开始时会忽略一个关键点TreeNode本身既是“树的一部分”也完全可以被看作“一棵独立的子树”。因为二叉树的定义是递归的任意一个节点往下都能形成结构完整的子树。所以思考树问题时先把视角收窄到当前节点和它的左右孩子剩下的让递归去处理这就是二叉树算法最核心的思维方式。不要急着背模板。先建立“当前节点 左子树 右子树”这样的心智模型。后续什么前序、中序、后序、层序本质上都只是对这个模型的访问顺序做了调整。1.2 空节点是递归的出口也是很多题目的分水岭递归写树题第一个永远要处理的往往是对空节点的判断。一个节点是null时应该返回什么这取决于题目问什么求最大深度时null对应的深度是 0。判断路径和是否存在时null通常意味着“这条路不存在”返回false。做树的序列化时null要显式编码成一个占位符。判断两棵树是否相同时两棵同时为null才算是相同。同样一个空指针在不同语义下返回值完全不同。别把“遇到空节点返回 0”这种习惯套到所有题目上先搞清楚题目里“空”代表什么含义否则会出现边界错误。我还建议在写递归函数的开头就写好空值分支不要等到递归深入才开始想。这能帮你把注意力集中在当前节点的处理上避免递归爆栈或空指针后一脸茫然。2. 遍历是树的根改两三行代码就是一个新题2.1 先讲递归遍历前序遍历、中序遍历、后序遍历三种递归遍历代码量极少差异只在访问当前节点的时机。// 前序遍历根 - 左 - 右 public void preorder(TreeNode root, ListInteger res) { if (root null) return; res.add(root.val); preorder(root.left, res); preorder(root.right, res); } // 中序遍历左 - 根 - 右 public void inorder(TreeNode root, ListInteger res) { if (root null) return; inorder(root.left, res); res.add(root.val); inorder(root.right, res); } // 后序遍历左 - 右 - 根 public void postorder(TreeNode root, ListInteger res) { if (root null) return; postorder(root.left, res); postorder(root.right, res); res.add(root.val); }前序遍历的结果顺序是“根、左、右”所以你第一次看到某个节点时就能处理它。中序遍历在二叉搜索树里极其重要因为中序输出天然是一个有序序列。后序遍历则经常用于先从子树收集信息、再回头处理根节点的场景比如求二叉树直径、删除节点这类题目。我习惯把“访问节点的时机”理解为递归调用执行的顺序先输出就是前序夹在左右递归之间就是中序放在两个递归之后就是后序。不需要硬背只要脑子里模拟一个小树跑一遍代码顺序自然就出来了。2.2 迭代前序和后序栈里谁先被弹出谁就先被访问递归本质上依赖系统栈。面试里常常会追问“不用递归怎么写”这时候显式栈就派上用场。很多人一上来就想同时模拟三种遍历结果把自己绕晕。我建议分两步先接受前序和中序的顺手写法再单独记后序的技巧。前序遍历迭代版核心是入栈顺序先压右孩子再压左孩子。因为栈是后进先出先压入右孩子左孩子才会被先弹出。public ListInteger preorderTraversal(TreeNode root) { ListInteger res new ArrayList(); if (root null) return res; DequeTreeNode stack new ArrayDeque(); stack.push(root); while (!stack.isEmpty()) { TreeNode cur stack.pop(); res.add(cur.val); if (cur.right ! null) stack.push(cur.right); if (cur.left ! null) stack.push(cur.left); } return res; }后序遍历迭代版有个非常巧的办法前序遍历是“根、左、右”后序遍历是“左、右、根”。如果先按“根、右、左”的顺序遍历再把整个结果反转就变成“左、右、根”。实现时只需要把前序遍历里左右孩子的压栈顺序对调然后拿一个链表从头部插入结果。public ListInteger postorderTraversal(TreeNode root) { LinkedListInteger res new LinkedList(); if (root null) return res; DequeTreeNode stack new ArrayDeque(); stack.push(root); while (!stack.isEmpty()) { TreeNode cur stack.pop(); res.addFirst(cur.val); if (cur.left ! null) stack.push(cur.left); if (cur.right ! null) stack.push(cur.right); } return res; }这段代码我第一次看时很困惑为什么结果能用addFirst反着插原因就是前面说的“反转对应关系”。后序遍历不要求你一次写对但建议理解它是从前序演变来的这样即使面试现场忘了也可以现场推出来。中序遍历的迭代写法稍微复杂一些因为要先一路压左子树到底再处理根节点。常见的模板是“左到底、弹栈、转右”这在二叉搜索树的题目里用得比较多例如找第 K 小的节点。2.3 层序遍历用队列层级信息藏在 size 里层序遍历也叫宽度优先遍历和栈的思路完全反过来用队列先处理当前层再向下一层推进。public ListListInteger levelOrder(TreeNode root) { ListListInteger res new ArrayList(); if (root null) return res; QueueTreeNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { int size queue.size(); ListInteger level new ArrayList(); for (int i 0; i size; i) { TreeNode cur queue.poll(); level.add(cur.val); if (cur.left ! null) queue.offer(cur.left); if (cur.right ! null) queue.offer(cur.right); } res.add(level); } return res; }这里最需要强调的就是int size queue.size();这一行。如果不先把当前层的节点数存下来循环过程中队列的size()是动态变化的你根本无法分清楚哪些节点属于同一层。层序遍历的变化题很多锯齿形层序遍历、每层最右节点、二叉树的最大宽度等底层都是同一个模板只是对每一层的处理方式不同。3. 从深度到路径递归返回值的常见套路3.1 最大深度是树里最朴素的“子问题”求二叉树最大深度是入门题但它的思想贯穿很多困难题public int maxDepth(TreeNode root) { if (root null) return 0; int leftDepth maxDepth(root.left); int rightDepth maxDepth(root.right); return Math.max(leftDepth, rightDepth) 1; }每个节点都在问同一句话我左子树有多深我右子树有多深取更大的那一个再加上当前节点这一层。加 1 是因为当前节点本身贡献了一个深度。基于这个结构能衍生出很多题目。判断平衡二叉树时不能在递归里对每个节点单独求一次深度再比较那样复杂度会变成 O(n^2)。更好的做法是把“子树是否平衡”和“子树高度”放在同一个递归里返回例如递归函数返回树的高度遇到不平衡情况就直接返回-1作为标记。这样每个节点只访问一次复杂度是 O(n)。3.2 最小深度与叶子节点的关系最小深度有坑。如果直接把最大深度代码里的Math.max改成Math.min遇到单边树时会出错。原因是最小深度的定义是到最近叶子节点的距离而叶子节点要求左右子树都为空。举个例子一棵只有左链的树比如路径依次是 1、2、3右侧全是空。按照错误的写法在节点 1 处右子树返回 0于是“最小深度”直接变成 011。但节点 1 本身并不是叶子真正的叶子是 3。所以处理最小深度时要先判断孩子是否为空再决定递归方向。public int minDepth(TreeNode root) { if (root null) return 0; if (root.left null root.right null) return 1; if (root.left null) return minDepth(root.right) 1; if (root.right null) return minDepth(root.left) 1; return Math.min(minDepth(root.left), minDepth(root.right)) 1; }这道题是典型的“空节点语义”陷阱。看起来只是在改一个函数名实际上你要先想清楚空节点在“最短路径”这个语境里意味着什么。3.3 路径和与路径本身返回值和“全局兜底”的分工路径类题目的另一种考法是“从根到叶子是否存在某条路径路径和等于 target”。典型写法是边遍历边减目标值public boolean hasPathSum(TreeNode root, int targetSum) { if (root null) return false; targetSum - root.val; if (root.left null root.right null) { return targetSum 0; } return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum); }我比较喜欢“剩余目标值”这种理解方式从根走到当前节点已经消耗了一部分目标剩下多少交给子树去判断。递归返回值在这里就是布尔值只要任意一条路径成立就为真。但如果题目要求返回所有满足条件的路径那返回值本身就装不下路径数据了。这时只能借助外部容器保存路径递归进去时添加节点递归出来时删除节点也就是回溯。切记回溯时一定要把刚才添加的节点移除否则路径会越积越长。这种“添加-递归-回溯”三件套在二叉树里出现频率非常高建议专门练习几道题形成肌肉记忆。3.4 二叉树直径答案可能在任意子树中间直径是后序遍历思想的经典应用。直径的定义是任意两个节点之间路径上边的数量它不一定经过根节点。所以递归时不能只返回“最大深度”还要维护一个全局最大值记录左右子树深度之和。int diameter 0; public int diameterOfBinaryTree(TreeNode root) { depth(root); return diameter; } private int depth(TreeNode root) { if (root null) return 0; int left depth(root.left); int right depth(root.right); diameter Math.max(diameter, left right); return Math.max(left, right) 1; }这个题给我的启发很大有些答案不在递归返回值里而是在递归过程的中间状态里。后序遍历天然适合“先收集左右子树信息再决定当前节点怎么处理”的场景。凡是题目和路径长度、最大利益、最深叶子相关都可以第一时间往后序递归上靠。4. 二叉搜索树特殊的顺序特殊的处理方式4.1 验证 BST 时别只判断左 根 右验证二叉搜索树的常见误区是只比较当前节点和左孩子、右孩子的大小。实际上 BST 的要求是“左子树的所有节点都小于根右子树的所有节点都大于根”。只比较相邻节点无法发现“右子树的左孩子比根还小”这类问题。正确做法是给每个节点传递一个范围区间min, max根节点初始范围是无穷小到无穷大向左走更新最大值为当前节点值向右走更新最小值为当前节点值public boolean isValidBST(TreeNode root) { return validate(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean validate(TreeNode node, long low, long high) { if (node null) return true; if (node.val low || node.val high) return false; return validate(node.left, low, node.val) validate(node.right, node.val, high); }另一种思路是利用中序遍历BST 的中序序列必然严格递增。你可以维护一个前驱节点在中序遍历过程中和前驱比较一旦当前值小于等于前驱值直接返回 false。这种方式不用额外保存整个遍历结果空间上更省。4.2 BST 的插入和删除递归返回的是“新树的根”插入 BST 很简单难的是删除。删除一个节点分三种情况节点是叶子直接返回 null 给上层。节点只有一个孩子返回那个孩子替代当前节点。节点有两个孩子可以在右子树中找到最小节点也可以找左子树中的最大节点用其值替换当前节点再递归删除那个用于替换的节点。实现删除时一个关键认知是递归函数的返回值要作为当前节点的左或右孩子接住。例如root.left deleteNode(root.left, key);这行代码不是在修改孩子值而是在告诉上层“删除后新的左子树是什么”。如果不接住返回值树结构调整后上层节点仍然指着老节点删除就会失败。public TreeNode deleteNode(TreeNode root, int key) { if (root null) return null; if (key root.val) { root.left deleteNode(root.left, key); } else if (key root.val) { root.right deleteNode(root.right, key); } else { if (root.left null root.right null) { return null; } else if (root.left null) { return root.right; } else if (root.right null) { return root.left; } else { TreeNode successor findMin(root.right); root.val successor.val; root.right deleteNode(root.right, successor.val); } } return root; }很多人在这一步卡很久核心就是把“修改树结构”理解成“返回一片新子树”再用上一层去接住。树的结构性操作比如翻转、合并、删除节点都要习惯这种写法。4.3 中序遍历在 BST 题里的统治力BST 有序这个性质能解决很多题目。求第 K 小元素就是按中序遍历走到第 K 个节点时停下。把二叉搜索树转换为累加树也可以中序遍历时累加节点值。甚至判断两棵 BST 是否结构相同也可以把中序序列拿出来比较。实际上只要题目出现 BST第一反应就应该看中序遍历。如果中序遍历能直接解决那就不要额外设计复杂递归了。如果中序解决不了再考虑递归分裂和范围判断。5. 重建与序列化把树变成可复用的数据再变回来5.1 前序 中序重建二叉树靠的是中序切分左右给定前序遍历和中序遍历可以唯一确定一棵二叉树。前序的第一个元素是根这个根把中序序列切成两半左边是左子树节点右边是右子树节点。有了左右子树的节点数量再回到前序中切出对应的区间递归下去即可。实现时比较重要的是下标计算。建一个HashMap保存中序各值的位置寻找根位置时就能从 O(n) 降到 O(1)。public TreeNode buildTree(int[] preorder, int[] inorder) { MapInteger, Integer pos new HashMap(); for (int i 0; i inorder.length; i) { pos.put(inorder[i], i); } return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, pos); } private TreeNode build(int[] pre, int preL, int preR, int[] in, int inL, int inR, MapInteger, Integer pos) { if (preL preR || inL inR) return null; TreeNode root new TreeNode(pre[preL]); int rootIndex pos.get(root.val); int leftCount rootIndex - inL; root.left build(pre, preL 1, preL leftCount, in, inL, rootIndex - 1, pos); root.right build(pre, preL leftCount 1, preR, in, rootIndex 1, inR, pos); return root; }这里最容易出错的是边界区间两端能否取到取决于左右子树是否为空。我习惯把所有递归函数的区间一律定义为“闭区间”然后每一层都遵守同一个约定这样推导起来不容易乱。判断终止条件时同时检查前序和中序区间是否失效双保险。5.2 序列化与反序列化用 null 占位顺序就不会丢序列化时前序遍历带上空节点占位后反序列化的还原顺序就是唯一的。比如某个节点是 null就写成null这样反序列化时读到一个 null就知道当前分支结束可以立刻返回。public String serialize(TreeNode root) { StringBuilder sb new StringBuilder(); se(root, sb); return sb.toString(); } private void se(TreeNode root, StringBuilder sb) { if (root null) { sb.append(null,); return; } sb.append(root.val).append(,); se(root.left, sb); se(root.right, sb); } public TreeNode deserialize(String data) { String[] arr data.split(,); QueueString queue new LinkedList(); for (String s : arr) queue.offer(s); return de(queue); } private TreeNode de(QueueString queue) { String val queue.poll(); if (val.equals(null)) return null; TreeNode node new TreeNode(Integer.parseInt(val)); node.left de(queue); node.right de(queue); return node; }序列化的实战场景不只是面试。很多系统在做缓存、跨服务传输时都会把树形结构序列化成字符串或字节流。关键是记住光按某种顺序存节点值不够必须把缺失的孩子用 null 标记出来否则还原时无法判断哪里该停。队列在这里的作用是保证反序列化顺序和前序序列完全一致每次 poll 一个值就生成一个节点顺序天然就是前序。5.3 扩展层序序列化也能还原二叉树层序序列化同样可行。按层序遍历顺序把节点拼接成字符串空节点用null占位。反序列化时用一个队列存储已创建的节点依次为队首节点挂载左右孩子创建完成后又把孩子入队。这种方式直观不需要递归但要注意队列里存的应该是“等待被挂接孩子的节点”而不是“待读取字符串里的节点”两者很容易混。6. 最近公共祖先与空间优化树的解法不止一种路径6.1 最近公共祖先的递归判定最近公共祖先这类题很考察递归理解。从根出发把查找看成“在左右子树里找目标节点”如果当前节点就是 p 或 q那当前节点就是公共祖先。如果 p、q 分别出现在左右子树中那当前节点就是答案。如果只在一侧找到递归结果直接向上返回。代码写出来非常短public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root null || root p || root q) return root; TreeNode left lowestCommonAncestor(root.left, p, q); TreeNode right lowestCommonAncestor(root.right, p, q); if (left ! null right ! null) return root; return left ! null ? left : right; }很多人第一次看这段代码会怀疑如果 p 和 q 都在同一侧岂不是会返回一个“不是公共祖先”的节点其实不会。递归向上返回时只有两侧都非空当前节点才会被确认为公共祖先如果只有一侧有结果说明公共祖先在那一侧更深的位置这个结果会一路向上传不会被中途拦截。6.2 父指针映射法把树当成无向图如果题目允许多次查询或者给定的是“任意两个节点之间的路径”用父节点映射会更直观。先通过一次 BFS 或递归记录每个节点的父节点然后从 p 节点出发将路径上的节点放入集合再从 q 节点向上走找到第一个命中集合的节点。这种方法的优点是好理解缺点是额外空间是 O(n)。如果面试官追问“能不能不用额外空间”再回落到上面那个递归版本。两个方案其实互补一个是普通解法一个是优雅解法。6.3 Morris 遍历把空间压到 O(1)Morris 遍历的核心思路是利用空指针做线索。中序遍历时找到当前节点左子树的最右节点把它的右指针临时指向当前节点。这样遍历过程中不需要栈也不需要递归空间复杂度是 O(1)代价是每个节点会被多访问常数次。Morris 遍历代码写出来不容易一次记牢但非常适合作为思考进阶题。面试中不一定要默写出来但你至少要知道“有一种不用栈的遍历方式”。如果遇到不允许改树结构、又要求 O(1) 空间的题目Morris 就是一个面试加分项。public ListInteger morrisInorder(TreeNode root) { ListInteger res new ArrayList(); TreeNode cur root; while (cur ! null) { if (cur.left null) { res.add(cur.val); cur cur.right; } else { TreeNode pre cur.left; while (pre.right ! null pre.right ! cur) { pre pre.right; } if (pre.right null) { pre.right cur; cur cur.left; } else { pre.right null; res.add(cur.val); cur cur.right; } } } return res; }理解这段代码时我建议在一棵小树上逐步画一遍。第二次碰到同一根线索时说明左子树已经处理完这时要断开线索、访问当前节点、再转右。如果没断开线索树结构就被临时修改了后续逻辑会出错。7. 二叉树实操注意事项与自查清单7.1 递归返回值的语义要固定写递归函数前先问自己一个明确问题这个函数到底返回什么是子树高度是是否存在目标节点是删除后的新根返回值语义不同写法差别很大。我见过最常见的翻车现场是这样的判断一个树是不是平衡树递归函数只返回 boolean结果每个节点都要重新计算高度整棵树复杂度变成 O(n^2)。正确的做法是把高度作为返回值用-1表示不平衡。这样“返回值的语义”就不是一个单纯的 boolean而是“带状态的高度”复杂度一次遍历能解决。7.2 判断叶子节点一定不要只看 null很多题目的终止条件是“到达叶子节点”但“叶子”严格定义是节点左右孩子都为空。空节点和叶子是两回事。在用递归求路径、判断路径和时先判断当前节点是否为空然后再判断左右孩子是否都为空顺序不能乱。尤其注意root null和root.left null这两种判断无法合并。实际操作中我习惯把空值判断放在函数最前面把“叶子判断”放在空值判断之后避免把空节点误当成叶子。7.3 迭代遍历里栈和队列的处理顺序最容易错前序遍历迭代中压栈顺序是先右后左因为栈是后进先出。很多第一次写的人下意识先压左结果输出顺序变成“根、右、左”和想象完全不同。后序遍历的“反转法”也容易错在addFirst方向上。我建议把代码分成两步记先牢牢记住前序遍历的迭代模板再在后序遍历时把前序遍历的“左孩子右孩子压栈顺序对调”同时使用addFirst插入结果。这样只需要记忆一组模板就能推导出另一种遍历。7.4 树形 DP 与全局变量的取舍遇到“最大路径和”“最长路径”“最大收益”这类题递归函数往往返回一个相对局部的值但最终答案用全局变量记录。这种模式在小范围测试时没问题但如果递归函数会被外部重复调用一定要在每次调用前把全局变量重置。我有一段时间被这个坑耽误过写一个工具方法内部类维护了一个max变量结果连续调用两次后结果越来越大。排查后发现是第二次调用没有重置上一次的全局值。凡是带全局变量的树算法建议要么把全局变量封装到内部方法中要么在入口处显式重置不要想当然地认为每次输入都是全新的。7.5 做题时给自己留一个自查顺序我自己的实操顺序是这样先画一棵三层左右的小树把普通情况跑一遍再画一棵单边树检查空子树是否会干扰深度或路径最后画一棵只有根节点的树确认边界 case。三步走完再提交代码。这个过程看起来慢但能省下大量调试时间。场景检查重点普通三层满树递归顺序、左右子树的调用是否正确单边树最小深度、平衡判断、路径类题目是否误判只有根节点叶子判断、返回值初始值是否合理空树入口函数是否直接返回正确结果最后再分享一个小经验二叉树题目看起来很多拆开后其实就几大类遍历、深度、路径、BST、重建、公共祖先。每类背后都有相对固定的递归模型。我在实际写代码过程中最大的体会是不要追求一次把代码写完美先写出“能对上语义”的版本再逐步优化空间和边界。很多看似很难的树题真正卡住人的不是代码本身而是对空节点和递归返回值的理解。把这两个地方想透很多题做起来会顺很多。