1. 先聊清楚为什么是树与二叉树每道题都值得按这套结构来写真正下定决心系统整理“树与二叉树”这个专题是我刷题进行到中间阶段时的事。刚开始我也是一股脑地刷今天做链表明天做动态规划回头发现树这块的题明明做过不少碰到变形题还是反应不过来。后来我把树与二叉树的所有题目全部按同一种模板重写了一遍也就是你看到的“完整题目描述 多组示例附解释 解题思路 带注释 Java 代码 复杂度分析”的结构。每道题都这样记录坚持了一段时间后确实产生了质变。为什么是这个专题如果你看过一些招聘笔试、软考真题会发现树与二叉树几乎是必出现的数据结构。它既不像数组、链表那样直观也不像图那样复杂到难以建模但它天然适合用来考察递归思想、遍历框架、迭代控制、问题分解能力是算法基础里承上启下的关键一环。掌握了树很多后续的复杂结构再展开都会轻松许多。至于为什么每道题都要坚持五要素完整记录是因为“看得懂题解”和“能自己描述清楚”之间隔着一段不小的距离。把题目原样抄一遍逼自己把边界条件梳理出来把示例多列几组尤其是那种带 null、带负数、只有一个根节点的特例其实就是在提前做边界思考把思路用文字写下来很多“我感觉会做”的题会瞬间露出破绽。Java 代码和详细注释则是为了让自己以后扫一眼就能拾起回忆而不是每次重头推演一遍。这套方式看起来很繁琐但它把一道题刷出了讲一遍给别人听的强度效果比单纯“看 默写代码”强得多。2. 树的遍历整个专题的第一道分水岭2.1 为什么不建议一上来就背模板很多刷题攻略喜欢直接给前中后序遍历的代码模板尤其简化成“递归三行、迭代三行”这种助记式写法。我并不是反对模板而是建议你在背模板之前先把遍历的本质搞清楚。树的递归遍历套路其实非常简单把每个非空节点当成一棵独立的子树访问根节点、递归处理左子树、递归处理右子树三件事的顺序改变一下就产生三种遍历顺序。前序就是根 - 左 - 右中序是左 - 根 - 右后序是左 - 右 - 根。这三个顺序听上去简单但在工程和面试里往往以变形题的方式出现比如“验证二叉搜索树”依赖中序有序“求二叉树直径”依赖后序收集左右子树信息“构造二叉树”依赖前序找根。如果只记模板而不理解访问时机变形题一出就容易卡住。理解前中后序还有一个很好用的思路把自己想象成一个深度优先的访问者每次遇到根节点时都有三个动作可以做分别是“经过根节点时记录”“从左子树回来时记录”“从右子树回来时记录”。前中后序本质上只是选择了这三个不同时机去读取节点值。理解到这一层前中后序就不再是三套需要分别背诵的逻辑而是同一套递归流程里的三个观测窗口。2.2 从递归到迭代用栈显式维护调用关系递归代码简洁但有一些场景偏偏要求用迭代实现比如不想让递归深度过大或者面试官明确要求空间复杂度 O(1) 之下的变体。这时候就需要明白一个基本事实递归本质上是系统在维护一个隐式的栈把每一层调用的局部变量和返回位置压进去迭代写法只是把这个栈从系统栈搬到了我们自己的变量里逻辑上并没有改变遍历顺序。以前序遍历为例迭代写法需要先把根节点压入栈中然后循环弹出栈顶节点访问。要保证弹出的顺序是“根、左、右”由于栈的后进先出特性需要往栈里先压右子节点再压左子节点。很多新手第一次写的时候顺序搞反得到的结果就变成了“根、右、左”。这段带注释的 Java 代码是我自己项目笔记里保留的版本public ListInteger preorderTraversal(TreeNode root) { ListInteger result new ArrayList(); if (root null) { return result; } DequeTreeNode stack new LinkedList(); stack.push(root); while (!stack.isEmpty()) { TreeNode node stack.pop(); // 前序遍历先访问根节点 result.add(node.val); // 因为栈是后进先出所以先压右树再压左树 if (node.right ! null) { stack.push(node.right); } if (node.left ! null) { stack.push(node.left); } } return result; }这里有一个很容易踩的坑不少文章推荐用Stack类但 Java 官方其实更建议使用ArrayDeque或LinkedList当栈用。Stack继承自Vector包含了大量与栈无关的旧接口并发和性能上并不理想。刷题阶段可能感觉不到差异但如果去公司做代码评审那这就是一眼能看出来的坏味道。中序和后序的迭代写法比前序麻烦一点关键区别在于中序需要先走到最左下角再逐个弹栈访问后序则可以用“根右左”的反向思路处理或者维护一个 prev 指针来判断右子树是否已经被处理完。一开始不建议贪多把前序吃透再写中序时重点理解“先深入左子树”的过程写后序时重点理解“访问左右子树之后再回到根”整体就会顺手很多。2.3 层序与二叉树的空节点表示除了深度优先的三种遍历层序遍历BFS在树与二叉树的很多题目中同样高频出现。它的实现比前中后序更容易理解借助队列先把根节点入队然后循环弹出队头节点把它的左右孩子依次入队。队列天然保证了同一层的节点按从左到右的顺序被取出。在刷题记笔记时题目给出的输入经常并不是一棵直观的树而是一个数组比如[3,9,20,null,null,15,7]它表示的其实是层序遍历序列null表示对应位置没有节点。这个约定非常有用因为它很简洁但也带来两个问题第一反推树结构时不能简单地把数组下标当成完全二叉树的父子关系第二把一棵树转换回数组时末尾会出现大量 null需要及时截断。理解“数组形式的树”是很重要的基本功因为后文要讲的序列化、反序列化以及在 IDE 里自己构造测试用例都离不开这套表示方式。我自己整理笔记时习惯把所有示例都写两个版本一个用数组形式方便肉眼检查另一个如果涉及反序列化就补成真正的树结构图。这样既能确保代码能跑通也能直观地在人脑中模拟递归过程。3. 树的属性与路径题大多数解法都在靠“后序归并”这一个思想3.1 深度、直径与平衡子树返回什么信息由父节点需要什么决定树的题目数量非常多但如果把核心题型梳理一下会发现相当大一部分都可以归结为“在遍历过程中收集子树信息回到当前节点时再做一次合并判断”。这类题写起来之所以难不是因为代码本身复杂而是递归函数返回值和题目要求的答案之间往往隔着一层转换。举一个最常见的例子求二叉树的最大深度。递归函数可以定义成“返回以当前节点为根的子树最大深度”对于空节点返回 0非空节点返回左右子树深度的最大值再加一。这个过程很直观但为什么它能正确工作因为每个节点都在重复做一件相同的事先让左右子树分别告诉“我有多高”然后取较大的一个把自己这一层的高度算进去再向上传递。再比如判断平不平衡平衡二叉树的定义是每个节点的左右子树高度差不超过一。如果沿用最大深度的思路可以先写一个求高度的函数然后在每个节点分别调用它求左右子树高度并判断差值这就是最朴素的解法。但这样每个节点都会重复计算子树高度复杂度到了 O(n log n)。更聪明的做法是改造求高度的递归函数正常情况下返回子树高度当发现某棵子树不平衡时用一个特殊值表示“这里已经出错了”然后让上层立刻感知并继续向上传播失败。上面在代码里我用过-1作为哨兵这就是最典型的空间换时间的后序归并思想。public boolean isBalanced(TreeNode root) { return height(root) ! -1; } private int height(TreeNode node) { if (node null) { return 0; } int left height(node.left); // 左子树已经不满足平衡条件提前结束 if (left -1) { return -1; } int right height(node.right); if (right -1) { return -1; } // 当前节点左右子树高度差超过1返回-1表示整棵树不平衡 if (Math.abs(left - right) 1) { return -1; } return Math.max(left, right) 1; }这种把“局部失败”放到返回值里层层传递的做法在树类题目中出现频率极高。它和很多状态压缩、动态规划的思路是相通的先让子树处理完自己的问题只向上层返回一个精简结论而不是把整棵子树的现场都搬出来。根据我的经验做题时遇到“需要判断所有子树都满足某个条件”的题目可以先想想让递归函数返回什么最省事再看能不能用一个标志值伪装成结果返回。3.2 最近公共祖先从路径对比到一次遍历搞定树里另一类绕不开的题目是路径与祖先问题其中最典型的是求两个节点的最近公共祖先LCA。初学者最容易想到的思路是分别从根节点出发找到通往 p 和 q 的路径再对比两条路径找到最后一个相同的节点。这个方案很好理解但需要额外的路径存储。更简洁的解法其实同样依赖后序归并。递归函数可以设计成如果当前节点是 p、q 中的任意一个或者当前节点为空直接返回当前节点否则分别去左子树和右子树里找。如果左右返回值都不为空说明 p 和 q 正好分散在当前节点的两侧那么当前节点就是最近公共祖先如果只有一侧不为空说明 p 和 q 都在那一侧子树中继续把那一侧的结果向上传递。public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // 当前节点为空或者直接命中了p/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) { // 如果左右都非空说明p和q分别位于当前节点两侧 return root; } // 哪边非空就返回哪边的结果 return left ! null ? left : right; }这段代码里有一个值得反复思考的点为什么“左右都非空”时当前节点就是最近公共祖先而不是某个更高的节点因为我们是自底向上处理的如果更高的某个祖先也是两侧都有 p 和 q那这一层早就该返回了根本不会把两个非空结果同时传上去。也就是说递归的返回路径天然地保证了我们找到的是最低的那个分叉点。3.3 一道综合题的完整练习样本这里分享一道我笔记里经常拿来当模板的综合题求二叉树中的最大路径和。路径被定义为从任意节点出发沿着父子连接走到任意节点的序列路径至少包含一个节点且不一定经过根节点。这个题和“求直径”“求最大子树和”非常类似核心依旧是后序归并但坑在于路径不能同时走左右两侧再向上延伸。每个节点向上返回的时候只能选择左子树方向或右子树方向中较大的那个分支加上当前节点值作为一个可以继续向上拼接的“半条路径”。但在更新全局最大值时则可以把左、右、当前节点值三者都加起来形成一条完整穿过当前节点的路径。我用伪代码复盘时的关键判断public int maxPathSum(TreeNode root) { int[] max new int[] { Integer.MIN_VALUE }; dfs(root, max); return max[0]; } private int dfs(TreeNode node, int[] max) { if (node null) { return 0; } int left Math.max(0, dfs(node.left, max)); int right Math.max(0, dfs(node.right, max)); // 穿当前节点的完整路径 max[0] Math.max(max[0], left right node.val); // 向上延伸时只能选择一条更优的分支 return Math.max(left, right) node.val; }这题能顺利写出来基本说明后序归并思想已经入门了。唯一要提醒的是“负节点”的情况如果子树返回值是负数向上拼接反而会拖累总和所以取Math.max(0, ...)这个动作等同于主动放弃负收益分支。初学时很容易忘记这个细节导致整棵树只有一个负节点时结果依然正确而多个负节点时输出完全不对。4. 树的构造与序列化反复打磨“根节点怎么找”这个核心能力4.1 从前序与中序构造二叉树构造类题目和遍历类题目是一体两面的。如果不知道遍历顺序怎么来就很难理解怎么根据遍历顺序把树还原回去。前序 中序构造二叉树是一道非常经典的题它考察点在于能否利用前序确定根、中序划分左右子树。前序遍历的第一个节点一定是整棵树的根。拿到根节点值之后去中序遍历里找到它的位置中序中根左边的部分都属于左子树右边的部分都属于右子树。接下来就进入递归用同样的逻辑处理左子树区间和右子树区间。如果每次都在中序数组中线性查找根的位置最坏复杂度是 O(n²)所以更稳妥的做法是先把中序数组的值到下标映射存进哈希表查找时就是 O(1)。我当时写这段代码时边界条件很容易搞混为了防止出错统一用左闭右闭区间。下面这是我落过地的版本比较适合作为注释理解public TreeNode buildTree(int[] preorder, int[] inorder) { MapInteger, Integer inorderIndexMap new HashMap(); for (int i 0; i inorder.length; i) { inorderIndexMap.put(inorder[i], i); } return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inorderIndexMap); } private TreeNode build(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight, MapInteger, Integer map) { if (preLeft preRight) { return null; } // 前序第一个节点就是当前子树的根 TreeNode root new TreeNode(preorder[preLeft]); int inIndex map.get(root.val); int leftSize inIndex - inLeft; // 左子树节点个数 // 根据节点个数切分前序和中序区间 root.left build(preorder, preLeft 1, preLeft leftSize, inorder, inLeft, inIndex - 1, map); root.right build(preorder, preLeft leftSize 1, preRight, inorder, inIndex 1, inRight, map); return root; }这里最关键的边界理解是中序区间里根下标减去当前中序左边界得到的leftSize代表了左子树的节点个数。这个数量可以直接换算到前序区间里用来切分前序的左右子树起点。很多新手会去背“preLeft 1”“preLeft leftSize 1”这些下标但如果能理解左子树大小这些下标其实是可以当场推出来的。4.2 层序序列化空节点与截断问题序列化和反序列化是树与二叉树中比较接近真实工程的一类题目因为核心问题是“如何把一棵内存中的树变成一个可存储、可传输的字符串再把它恢复回原样”。常见的序列化方式有前序递归序列化、后序序列化、层序序列化等。在我整理过的题目里层序序列化是理解起来最直观但同时坑也最多的一种。层序序列化基本就是层序遍历的扩展普通层序遍历只把非空节点入队而序列化时需要把每个节点的左右孩子统统变成字符串输出即使是 null 也要输出为null。原因很简单如果遇到空节点不输出任何信息反序列化时无法区分“这个位置本来就空”和“这里根本没有输出位置”树的结构就会丢失。下面是我常用的序列化版本输出形式类似 LeetCode 风格的[3,9,20,null,null,15,7]public String serialize(TreeNode root) { if (root null) { return []; } QueueTreeNode queue new LinkedList(); queue.offer(root); StringBuilder sb new StringBuilder([); while (!queue.isEmpty()) { TreeNode node queue.poll(); if (node null) { sb.append(null,); } else { sb.append(node.val).append(,); queue.offer(node.left); queue.offer(node.right); } } return sb.substring(0, sb.length() - 1) ]; }这里有一个非常容易踩的细节节点非空时即使左右孩子是 null也必须把孩子入队而等到从队列中弹出 null 节点时又不需要再给 null 节点补“null 的孩子”了因为树到此已经到达叶子的边缘。如果把这层关系想通反序列化其实就是在队列里按顺序消费字符串数组。每弹出数组中的一个值就创建一个节点并把它挂到父亲节点指针上。反序列化的过程需要额外维护一个指针指向下一组要消耗的值这个过程和 BFS 是严格对齐的。序列化这类题的复杂度分析往往被忽略。很多人只写一句“O(n)”但实际字符串拼接过程隐藏着 O(n²) 的风险如果在循环里反复使用字符串拼接每次可能发生复制。上面代码选择StringBuilder就是这个原因。刷题阶段当然不是所有地方的性能都很敏感但“带注释的 Java 代码”本来就该说清楚每一处关键选型。4.3 构造题的共性前序/后序定位根中序划分子树构造类题目并不只有“前序 中序”这一种组合还包括“后序 中序”“层序 中序”、二叉搜索树的序列化与恢复以及根据 BST 的特性把字符串转树等。把这些题放在一起复盘会发现它们全都围绕一个核心先找到根再借助根在中序或顺序约束下的位置切分左右区间。不同之处在于如何定位根。前序序列的规律是“第一个元素为根剩下的区间先左后右”而后序序列则是“最后一个元素为根剩下的区间先左后右”。一旦定位到根总能用某种中序信息如果有提供或者 BST 的大小关系来切分区间。多做几道构造题以后会慢慢形成条件反射看到“某个序列符合顺序特征”第一反应不是去还原整棵树而是去找“根在哪左边界和右边界如何确定”。5. 二叉搜索树与 AVL从“能用”到“知道为什么能用”5.1 BST 的中序有序性质验证、查询与区间问题二叉搜索树BST的结构定义很简单对任意节点左子树所有节点值都小于当前节点右子树所有节点值都大于当前节点。这个定义带来的最大好处是中序遍历 BST 会得到一个严格递增的序列。因为这个性质很多与“顺序”“第 K 大”“区间范围”相关的题目都会考虑先做中序遍历再进行处理。验证一棵树是否为 BST 是基础中的基础。最容易犯的错误是只比较当前节点和左右孩子的大小关系比如觉得“只要 root.left.val root.val 且 root.right.val root.val 就行”。这个判断漏掉了更深层次的要求左子树中所有节点都必须小于当前节点而不只是直接左孩子。解决这个问题通常有两种思路第一种是中序遍历后检查得到的结果是否严格递增第二种是递归时给每棵子树限定一个上下界。第二种写法更通用也更能体现 BST 中“区间约束”的思想。public boolean isValidBST(TreeNode root) { return valid(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean valid(TreeNode node, long lower, long upper) { if (node null) { return true; } // 节点的值必须落在 (lower, upper) 开区间内 if (node.val lower || node.val upper) { return false; } return valid(node.left, lower, node.val) valid(node.right, node.val, upper); }为什么要用Long.MIN_VALUE而不用Integer.MIN_VALUE因为题目测试用例可能正好把 Integer 的最小值或最大值作为二叉树节点的值。如果初始上下界直接用了 Integer 的边界恰好节点值等于边界值时和的判断会直接误杀合法节点。这类问题在实际写代码时极容易忽略一旦样例里有边界值就翻车。多组示例的意义在这里体现得最直接设计测试用例时应当主动把最大值、最小值、重复值都覆盖进去。BST 的插入、查询、删除等操作也都是基于递归缩小搜索范围的思路进行的插入时可以沿着比较路径一路走到空位查询时就近比较大小决定去左还是去右。这些操作的时间复杂度都和树高相关如果 BST 退化成一条链就会退化成 O(n)。5.2 删除节点时Java 引用到底怎么处理BST 的删除操作是很多人觉得棘手的一道题难点在于要分三种情况讨论被删除节点没有左孩子、没有右孩子、同时有左右孩子。没有左右孩子属于空分支直接返回另一侧子树即可比较麻烦的是左右子树都存在的情况。此时必须找到被删除节点的后继右子树中的最小节点用后继节点的值覆盖删除节点的值然后递归去右子树中删除那个后继节点。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) { return root.right; } if (root.right null) { return root.left; } // 寻找右子树中最小的节点作为后继 TreeNode successor root.right; while (successor.left ! null) { successor successor.left; } root.val successor.val; root.right deleteNode(root.right, successor.val); } return root; }很多 Java 初学者在写“删除节点”时潜意识里觉得树操作能像删除数组或链表某个元素那样直接用一个引用把自己替换掉。实际上二叉树的节点之间有单向引用当前递归函数只能通过返回值告诉父节点“我这里已经变成谁了”。所以删除操作的本质是修改父节点对当前节点的引用除非当前节点本身就是根。这点想明白了就能理解为什么这个函数在有子节点时需要返回另一个节点而不是在方法内部做“自我清除”。在刷树题时“引用如何变化”往往比“具体值怎样变化”更重要。我一般看到root.left deleteNode(...)这种递归赋值语句都会刻意停下想一想赋值给左侧相当于父节点把左子树指针指向了新生成的子树根这样递归返回时整棵树的引用链才不会断掉。5.3 AVL 与更高阶的关联先把旋转的动机弄明白网络热词里经常混着“嵌入式 二叉树之avl树”说明 AVL 树不仅是数据结构书上的一章也是很多笔试面试里容易被提到的知识点。但说实话面试里手写完整 AVL 插入并做四种旋转的题目并不算特别高频更常见的考法是“给出一个插入后的局部结构判断该做哪种旋转”。软考等场景中也经常出现 AVL 建树、平衡因子计算这类问题。所以不建议一上来就背左旋右旋代码而是先理解为什么需要旋转。AVL 树的基本判定是每个节点的左右子树高度差绝对值不超过一。当插入或删除导致某个祖先节点平衡因子变成 ±2就必须调整。调整的核心思路是让“不平衡位置附近的三个节点重新排列成一个更均衡的形态”具体是左旋、右旋、左右双旋还是右左双旋取决于哪一侧更深。四种旋转代码并不复杂但如果不理解旋转是在改变父子关系、同时维护 BST 的中序顺序写的时候很容易在子树交接处漏掉一条引用。这一块和树与二叉树专题的刷题关系是延伸关系。建议后面的学习路径可以是先理解 BST 的查找和插入再手动模拟 AVL 在极端序列下自平衡过程最后重新写几遍旋转代码。单纯“看懂了”不会让你真正掌握必须动手在纸上画出每一步的节点引用变化。6. 复杂度分析不写清楚时间空间刷题就缺了最重要的一环6.1 时间复杂度别只写一个 O(n)对每道题给出复杂度分析看似是凑字数实际上是检验自己是否真懂这个算法的试金石。二叉树题目中大量递归函数的复杂度可以用递推式来表达。比如遍历一棵树时每个节点最多被访问常数次因此时间复杂度是 O(n)其中 n 是节点总数。但有些基础题会在递归内部再做一次遍历比如朴素平衡树判断在每个节点都调用一次求高度那就变成了每个节点都要对它下面的子树做一次完整遍历复杂度就是 O(n log n)平衡情况下甚至退化成 O(n²)。如果只笼统地写 O(n)等于没分析。判断一个数是否平衡、求最大路径和这类递归写法也可以从主定理角度理解。以前序遍历为例递归关系大约是 T(n) 2·T(n/2) O(1)理想平衡二叉树下根据主定理得到 O(n)。如果树的形状极端每次只向一侧递归则 T(n) T(n-1) O(1)时间复杂度依然是 O(n)主要的差别体现在空间上。所以在复杂度分析里时间复杂度和树的形状几乎没有变化真正区分度很高的是空间复杂度。6.2 空间复杂度递归栈到底算不算空间很多刷题库对空间复杂度的定义会特别说明递归时系统调用栈占用的空间要计算在内。我第一次学树题时也困惑过递归函数没有额外申请数组为什么空间复杂度不是 O(1)原因在于每次递归调用都会在系统栈上保存当前帧包括局部变量和返回地址在极端单链形态的树下递归深度能达到 n所以空间复杂度是 O(n)。平衡二叉树下递归深度大约是树高 O(log n)空间复杂度自然就是 O(log n)。迭代写法的空间消耗也同样要关注。显式使用栈的时候栈中最大元素个数取决于遍历状态最坏情况下接近 O(n)层序遍历使用队列时队列里最多会容纳某一层的全部节点满二叉树最后一层就有约 n/2 个节点所以空间复杂度同样是 O(n)。很多时候题目允许递归但面试官如果追加一句“能不能不用递归写”你要能回答清楚迭代版的额外空间来源是什么。6.3 常见题型复杂度速查整理笔记时我习惯给每种题型做一张复杂度速查表方便复习时快速回忆。这个习惯让我在复习多道树题时不需要从头再读一遍题解扫一眼表格就能把各种写法的代价串起来。题型常见写法时间复杂度空间复杂度关键说明前序/中序/后序遍历递归O(n)O(h)h 为树高极端链状时为 O(n)前序/中序/后序遍历迭代 栈O(n)O(n)显式栈最坏需要容纳全部节点层序遍历队列O(n)O(n)队列峰值约等于某一层最宽节点数二叉树最大深度后序递归O(n)O(h)每个节点访问一次平衡判断后序归并O(n)O(h)返回 -1 作为失败信号避免重复计算最大路径和后序归并O(n)O(h)全局变量保存整条路径最大值最近公共祖先后序递归O(n)O(h)命中 p/q 后直接向上返回从前序中序构造二叉树哈希表 递归O(n)O(n)哈希表空间 O(n)递归栈 O(h)验证二叉搜索树递归 上下界O(n)O(h)用 Long 边界避免 Int 边界误判BST 删除节点递归 寻找后继O(h)O(h)最坏退化为单链时 O(n)这张表里的空间复杂度都写了 O(h) 而不是固定的 O(log n)是因为树高本身不确定。很多初学者写复杂度时只会写平衡二叉树的情况却忽略了题目从来没有保证“这棵树是平衡的”。严谨一点应该区分“最坏情况”和“平均情况”否则面试反问时会露出破绽。6.4 从复杂度分析倒推优化方向复杂度分析不只是为了在笔记里写上一句话它是帮助你判断一道题是否还有更优解法的罗盘。举个例子如果先序遍历要用递归但是担心递归深度看到 O(h) 的空间复杂度就知道需要改成 Morris 遍历或迭代遍历才能进一步压缩空间如果验证 BST 选择先中序遍历再检查数组是否递增额外空间就是 O(n)改成上下界递归后空间降为 O(h)。这些判断不是靠背模板得来的而是靠“我想要优化某个指标”倒推出的目标。刷树题时比较推荐的做法是每做完一题都问自己三句话最坏情况下树退化成一条链我的代码能跑多深递归栈会不会爆能不能改成迭代版来减少线程栈压力这组问题在真实工程和笔试环境中都可能出现尤其在数据量巨大且不能依赖递归环境的情况下树的高递归深度会成为真正的瓶颈。7. 这一路踩过的坑代码之外的细节同样致命7.1 概念混淆与边界不清树与二叉树最大的概念坑是分不清“二叉树的深度”和“节点的高度”。有些题目里说深度有些说高度如果语义不统一代码容易写乱。从最常见的定义看根节点的深度一般是 0 或 1但不同题库可能从 0 开始也可能从 1 开始写代码前最好先通过示例反推。题目描述中如果给出了多组示例通常可以用示例去确认定义这正是“多组示例附解释”价值所在。另一个容易踩的坑是数组形式的输入里 null 的处理。对于一个类似[1,null,2,3]的输入它根本不是完全二叉树不能用2*i1和2*i2的数组公式去推导某个节点的左右孩子只能按层序遍历顺序重建。不少新手刚接触二叉树题目时会直接拿数组下标当树结构下标结果在构造和遍历的题目里越写越晕。正确做法是把数组先还原成节点对象再在以节点为单位的树上做递归。7.2 Java 代码里的高频运行时错误树类题目使用的是 Java 对象引用所以运行时错误也带有明显特征。最常见的当然是空指针而且往往发生在递归取node.left或node.right之前没有判空。这个问题在层序和迭代写法中尤其突出因为队列中允许存 null但循环体里可能直接访问node.val。应对方法不一定是每个地方都加空判断而是要在设计算法时明确“哪些节点永远不会为 null哪些位置会出现 null”。比如层序遍历弹出队列头时如果是 null就 continue如果节点非空再把左右孩子加入队列这样就能把空指针防御集中在入口处。第二种高频问题是整型溢出。求最大路径和、求 BST 的区间和等题目里初始值如果设为 0 可能无法正确处理全负数数据设为Integer.MIN_VALUE时如果中间做了减法又可能溢出。通常更稳妥的做法是使用 long 参与中间运算或者把初始最大值设置成一个能覆盖所有合法结果的极小值。现实中不少题目的测试用例会专门安排边界数值所以对比较敏感的数据范围一定要多做几组示例验证。第三类问题来自 Java 的“值传递”特性。很多人想在递归函数里更新一个全局最大值直接传一个 int 进去却发现递归返回后 int 没变。这是很经典的 Java 误区。解决办法无非三种用成员变量、用长度为 1 的数组包装、自定义一个可变容器对象。上面最大路径和的代码里我用了int[] max来保存全局答案原理就是数组对象本身引用不变只是内部元素被修改了。如果直接传intJava 是值传递改的只是栈上的副本不会影响外层变量。7.3 短路逻辑、搜索方向与遍历入口树的递归函数如果写了很多 if 分支要特别留意“短路”带来的行为变化。防止空指针常写node null || node.val target这个表达式因为短路逻辑左边为 true 时右边根本不会执行所以不会出现空指针。如果把条件顺序反过来写成node.val target || node null当 node 为 null 时就会立刻崩溃。代码规范课上经常会强调这一点但在递归里往往是最多发的低级 Bug。另一个方向性问题出现在二叉搜索树题目里。BST 每次比较后只能走一个方向搜索但如果是普通二叉树就不能根据数值大小跳过另一边。很多做熟 BST 题的人转到普通二叉树后容易下意识认为“直接比较左右即可”结果漏掉了应有的全面遍历。每次动手前先确认“当前这题里的树是不是 BST”这个判断能避免很多方向性失误。7.4 从“看懂题解”到“独立写出来”的检测方法我整理这套带注释 Java 代码的过程里最意外的一个收获是给代码写注释这件事本身就是最高效的检测工具。如果我发现某一段代码自己怎么也注释不清楚甚至想不出为什么变量要这样命名那就说明我其实并没有真正理解它。这时我会把题目放下第二天重新不看答案写一遍。还写不出来再回去认真读题解写得出来说明这个题才真正属于自己。针对树类题我还总结了一个快速复查的方法把同一道题的递归函数口头翻译成一句话。比如“isBalanced 返回的是当前子树是否平衡”这个一句话能不能说得通决定了代码内部逻辑是否自洽。如果发现一句话里要加很多额外的“但是”“还有”说明递归函数的职责还不明确需要重构。最后的建议是不要把“做的题数”当成绩效指标。刷 10 道只看一遍题解的题不如把 3 道题按完整模板整理好反复看三遍。树与二叉树这个专题尤其适合“少而深”的学习方式因为递归思想差一个环节没有想通下一道题照样会在同一个点卡住。对我而言这套完整结构化的记录帮我养成了稳定的解题习惯先描述题目与示例再定递归函数返回值然后推边界最后写代码和复杂度。现在看到一道新树题我基本能按这套流程快速判断难度和薄弱点在哪里。
树与二叉树刷题方法论：从遍历到构造与平衡的完整指南
1. 先聊清楚为什么是树与二叉树每道题都值得按这套结构来写真正下定决心系统整理“树与二叉树”这个专题是我刷题进行到中间阶段时的事。刚开始我也是一股脑地刷今天做链表明天做动态规划回头发现树这块的题明明做过不少碰到变形题还是反应不过来。后来我把树与二叉树的所有题目全部按同一种模板重写了一遍也就是你看到的“完整题目描述 多组示例附解释 解题思路 带注释 Java 代码 复杂度分析”的结构。每道题都这样记录坚持了一段时间后确实产生了质变。为什么是这个专题如果你看过一些招聘笔试、软考真题会发现树与二叉树几乎是必出现的数据结构。它既不像数组、链表那样直观也不像图那样复杂到难以建模但它天然适合用来考察递归思想、遍历框架、迭代控制、问题分解能力是算法基础里承上启下的关键一环。掌握了树很多后续的复杂结构再展开都会轻松许多。至于为什么每道题都要坚持五要素完整记录是因为“看得懂题解”和“能自己描述清楚”之间隔着一段不小的距离。把题目原样抄一遍逼自己把边界条件梳理出来把示例多列几组尤其是那种带 null、带负数、只有一个根节点的特例其实就是在提前做边界思考把思路用文字写下来很多“我感觉会做”的题会瞬间露出破绽。Java 代码和详细注释则是为了让自己以后扫一眼就能拾起回忆而不是每次重头推演一遍。这套方式看起来很繁琐但它把一道题刷出了讲一遍给别人听的强度效果比单纯“看 默写代码”强得多。2. 树的遍历整个专题的第一道分水岭2.1 为什么不建议一上来就背模板很多刷题攻略喜欢直接给前中后序遍历的代码模板尤其简化成“递归三行、迭代三行”这种助记式写法。我并不是反对模板而是建议你在背模板之前先把遍历的本质搞清楚。树的递归遍历套路其实非常简单把每个非空节点当成一棵独立的子树访问根节点、递归处理左子树、递归处理右子树三件事的顺序改变一下就产生三种遍历顺序。前序就是根 - 左 - 右中序是左 - 根 - 右后序是左 - 右 - 根。这三个顺序听上去简单但在工程和面试里往往以变形题的方式出现比如“验证二叉搜索树”依赖中序有序“求二叉树直径”依赖后序收集左右子树信息“构造二叉树”依赖前序找根。如果只记模板而不理解访问时机变形题一出就容易卡住。理解前中后序还有一个很好用的思路把自己想象成一个深度优先的访问者每次遇到根节点时都有三个动作可以做分别是“经过根节点时记录”“从左子树回来时记录”“从右子树回来时记录”。前中后序本质上只是选择了这三个不同时机去读取节点值。理解到这一层前中后序就不再是三套需要分别背诵的逻辑而是同一套递归流程里的三个观测窗口。2.2 从递归到迭代用栈显式维护调用关系递归代码简洁但有一些场景偏偏要求用迭代实现比如不想让递归深度过大或者面试官明确要求空间复杂度 O(1) 之下的变体。这时候就需要明白一个基本事实递归本质上是系统在维护一个隐式的栈把每一层调用的局部变量和返回位置压进去迭代写法只是把这个栈从系统栈搬到了我们自己的变量里逻辑上并没有改变遍历顺序。以前序遍历为例迭代写法需要先把根节点压入栈中然后循环弹出栈顶节点访问。要保证弹出的顺序是“根、左、右”由于栈的后进先出特性需要往栈里先压右子节点再压左子节点。很多新手第一次写的时候顺序搞反得到的结果就变成了“根、右、左”。这段带注释的 Java 代码是我自己项目笔记里保留的版本public ListInteger preorderTraversal(TreeNode root) { ListInteger result new ArrayList(); if (root null) { return result; } DequeTreeNode stack new LinkedList(); stack.push(root); while (!stack.isEmpty()) { TreeNode node stack.pop(); // 前序遍历先访问根节点 result.add(node.val); // 因为栈是后进先出所以先压右树再压左树 if (node.right ! null) { stack.push(node.right); } if (node.left ! null) { stack.push(node.left); } } return result; }这里有一个很容易踩的坑不少文章推荐用Stack类但 Java 官方其实更建议使用ArrayDeque或LinkedList当栈用。Stack继承自Vector包含了大量与栈无关的旧接口并发和性能上并不理想。刷题阶段可能感觉不到差异但如果去公司做代码评审那这就是一眼能看出来的坏味道。中序和后序的迭代写法比前序麻烦一点关键区别在于中序需要先走到最左下角再逐个弹栈访问后序则可以用“根右左”的反向思路处理或者维护一个 prev 指针来判断右子树是否已经被处理完。一开始不建议贪多把前序吃透再写中序时重点理解“先深入左子树”的过程写后序时重点理解“访问左右子树之后再回到根”整体就会顺手很多。2.3 层序与二叉树的空节点表示除了深度优先的三种遍历层序遍历BFS在树与二叉树的很多题目中同样高频出现。它的实现比前中后序更容易理解借助队列先把根节点入队然后循环弹出队头节点把它的左右孩子依次入队。队列天然保证了同一层的节点按从左到右的顺序被取出。在刷题记笔记时题目给出的输入经常并不是一棵直观的树而是一个数组比如[3,9,20,null,null,15,7]它表示的其实是层序遍历序列null表示对应位置没有节点。这个约定非常有用因为它很简洁但也带来两个问题第一反推树结构时不能简单地把数组下标当成完全二叉树的父子关系第二把一棵树转换回数组时末尾会出现大量 null需要及时截断。理解“数组形式的树”是很重要的基本功因为后文要讲的序列化、反序列化以及在 IDE 里自己构造测试用例都离不开这套表示方式。我自己整理笔记时习惯把所有示例都写两个版本一个用数组形式方便肉眼检查另一个如果涉及反序列化就补成真正的树结构图。这样既能确保代码能跑通也能直观地在人脑中模拟递归过程。3. 树的属性与路径题大多数解法都在靠“后序归并”这一个思想3.1 深度、直径与平衡子树返回什么信息由父节点需要什么决定树的题目数量非常多但如果把核心题型梳理一下会发现相当大一部分都可以归结为“在遍历过程中收集子树信息回到当前节点时再做一次合并判断”。这类题写起来之所以难不是因为代码本身复杂而是递归函数返回值和题目要求的答案之间往往隔着一层转换。举一个最常见的例子求二叉树的最大深度。递归函数可以定义成“返回以当前节点为根的子树最大深度”对于空节点返回 0非空节点返回左右子树深度的最大值再加一。这个过程很直观但为什么它能正确工作因为每个节点都在重复做一件相同的事先让左右子树分别告诉“我有多高”然后取较大的一个把自己这一层的高度算进去再向上传递。再比如判断平不平衡平衡二叉树的定义是每个节点的左右子树高度差不超过一。如果沿用最大深度的思路可以先写一个求高度的函数然后在每个节点分别调用它求左右子树高度并判断差值这就是最朴素的解法。但这样每个节点都会重复计算子树高度复杂度到了 O(n log n)。更聪明的做法是改造求高度的递归函数正常情况下返回子树高度当发现某棵子树不平衡时用一个特殊值表示“这里已经出错了”然后让上层立刻感知并继续向上传播失败。上面在代码里我用过-1作为哨兵这就是最典型的空间换时间的后序归并思想。public boolean isBalanced(TreeNode root) { return height(root) ! -1; } private int height(TreeNode node) { if (node null) { return 0; } int left height(node.left); // 左子树已经不满足平衡条件提前结束 if (left -1) { return -1; } int right height(node.right); if (right -1) { return -1; } // 当前节点左右子树高度差超过1返回-1表示整棵树不平衡 if (Math.abs(left - right) 1) { return -1; } return Math.max(left, right) 1; }这种把“局部失败”放到返回值里层层传递的做法在树类题目中出现频率极高。它和很多状态压缩、动态规划的思路是相通的先让子树处理完自己的问题只向上层返回一个精简结论而不是把整棵子树的现场都搬出来。根据我的经验做题时遇到“需要判断所有子树都满足某个条件”的题目可以先想想让递归函数返回什么最省事再看能不能用一个标志值伪装成结果返回。3.2 最近公共祖先从路径对比到一次遍历搞定树里另一类绕不开的题目是路径与祖先问题其中最典型的是求两个节点的最近公共祖先LCA。初学者最容易想到的思路是分别从根节点出发找到通往 p 和 q 的路径再对比两条路径找到最后一个相同的节点。这个方案很好理解但需要额外的路径存储。更简洁的解法其实同样依赖后序归并。递归函数可以设计成如果当前节点是 p、q 中的任意一个或者当前节点为空直接返回当前节点否则分别去左子树和右子树里找。如果左右返回值都不为空说明 p 和 q 正好分散在当前节点的两侧那么当前节点就是最近公共祖先如果只有一侧不为空说明 p 和 q 都在那一侧子树中继续把那一侧的结果向上传递。public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // 当前节点为空或者直接命中了p/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) { // 如果左右都非空说明p和q分别位于当前节点两侧 return root; } // 哪边非空就返回哪边的结果 return left ! null ? left : right; }这段代码里有一个值得反复思考的点为什么“左右都非空”时当前节点就是最近公共祖先而不是某个更高的节点因为我们是自底向上处理的如果更高的某个祖先也是两侧都有 p 和 q那这一层早就该返回了根本不会把两个非空结果同时传上去。也就是说递归的返回路径天然地保证了我们找到的是最低的那个分叉点。3.3 一道综合题的完整练习样本这里分享一道我笔记里经常拿来当模板的综合题求二叉树中的最大路径和。路径被定义为从任意节点出发沿着父子连接走到任意节点的序列路径至少包含一个节点且不一定经过根节点。这个题和“求直径”“求最大子树和”非常类似核心依旧是后序归并但坑在于路径不能同时走左右两侧再向上延伸。每个节点向上返回的时候只能选择左子树方向或右子树方向中较大的那个分支加上当前节点值作为一个可以继续向上拼接的“半条路径”。但在更新全局最大值时则可以把左、右、当前节点值三者都加起来形成一条完整穿过当前节点的路径。我用伪代码复盘时的关键判断public int maxPathSum(TreeNode root) { int[] max new int[] { Integer.MIN_VALUE }; dfs(root, max); return max[0]; } private int dfs(TreeNode node, int[] max) { if (node null) { return 0; } int left Math.max(0, dfs(node.left, max)); int right Math.max(0, dfs(node.right, max)); // 穿当前节点的完整路径 max[0] Math.max(max[0], left right node.val); // 向上延伸时只能选择一条更优的分支 return Math.max(left, right) node.val; }这题能顺利写出来基本说明后序归并思想已经入门了。唯一要提醒的是“负节点”的情况如果子树返回值是负数向上拼接反而会拖累总和所以取Math.max(0, ...)这个动作等同于主动放弃负收益分支。初学时很容易忘记这个细节导致整棵树只有一个负节点时结果依然正确而多个负节点时输出完全不对。4. 树的构造与序列化反复打磨“根节点怎么找”这个核心能力4.1 从前序与中序构造二叉树构造类题目和遍历类题目是一体两面的。如果不知道遍历顺序怎么来就很难理解怎么根据遍历顺序把树还原回去。前序 中序构造二叉树是一道非常经典的题它考察点在于能否利用前序确定根、中序划分左右子树。前序遍历的第一个节点一定是整棵树的根。拿到根节点值之后去中序遍历里找到它的位置中序中根左边的部分都属于左子树右边的部分都属于右子树。接下来就进入递归用同样的逻辑处理左子树区间和右子树区间。如果每次都在中序数组中线性查找根的位置最坏复杂度是 O(n²)所以更稳妥的做法是先把中序数组的值到下标映射存进哈希表查找时就是 O(1)。我当时写这段代码时边界条件很容易搞混为了防止出错统一用左闭右闭区间。下面这是我落过地的版本比较适合作为注释理解public TreeNode buildTree(int[] preorder, int[] inorder) { MapInteger, Integer inorderIndexMap new HashMap(); for (int i 0; i inorder.length; i) { inorderIndexMap.put(inorder[i], i); } return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inorderIndexMap); } private TreeNode build(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight, MapInteger, Integer map) { if (preLeft preRight) { return null; } // 前序第一个节点就是当前子树的根 TreeNode root new TreeNode(preorder[preLeft]); int inIndex map.get(root.val); int leftSize inIndex - inLeft; // 左子树节点个数 // 根据节点个数切分前序和中序区间 root.left build(preorder, preLeft 1, preLeft leftSize, inorder, inLeft, inIndex - 1, map); root.right build(preorder, preLeft leftSize 1, preRight, inorder, inIndex 1, inRight, map); return root; }这里最关键的边界理解是中序区间里根下标减去当前中序左边界得到的leftSize代表了左子树的节点个数。这个数量可以直接换算到前序区间里用来切分前序的左右子树起点。很多新手会去背“preLeft 1”“preLeft leftSize 1”这些下标但如果能理解左子树大小这些下标其实是可以当场推出来的。4.2 层序序列化空节点与截断问题序列化和反序列化是树与二叉树中比较接近真实工程的一类题目因为核心问题是“如何把一棵内存中的树变成一个可存储、可传输的字符串再把它恢复回原样”。常见的序列化方式有前序递归序列化、后序序列化、层序序列化等。在我整理过的题目里层序序列化是理解起来最直观但同时坑也最多的一种。层序序列化基本就是层序遍历的扩展普通层序遍历只把非空节点入队而序列化时需要把每个节点的左右孩子统统变成字符串输出即使是 null 也要输出为null。原因很简单如果遇到空节点不输出任何信息反序列化时无法区分“这个位置本来就空”和“这里根本没有输出位置”树的结构就会丢失。下面是我常用的序列化版本输出形式类似 LeetCode 风格的[3,9,20,null,null,15,7]public String serialize(TreeNode root) { if (root null) { return []; } QueueTreeNode queue new LinkedList(); queue.offer(root); StringBuilder sb new StringBuilder([); while (!queue.isEmpty()) { TreeNode node queue.poll(); if (node null) { sb.append(null,); } else { sb.append(node.val).append(,); queue.offer(node.left); queue.offer(node.right); } } return sb.substring(0, sb.length() - 1) ]; }这里有一个非常容易踩的细节节点非空时即使左右孩子是 null也必须把孩子入队而等到从队列中弹出 null 节点时又不需要再给 null 节点补“null 的孩子”了因为树到此已经到达叶子的边缘。如果把这层关系想通反序列化其实就是在队列里按顺序消费字符串数组。每弹出数组中的一个值就创建一个节点并把它挂到父亲节点指针上。反序列化的过程需要额外维护一个指针指向下一组要消耗的值这个过程和 BFS 是严格对齐的。序列化这类题的复杂度分析往往被忽略。很多人只写一句“O(n)”但实际字符串拼接过程隐藏着 O(n²) 的风险如果在循环里反复使用字符串拼接每次可能发生复制。上面代码选择StringBuilder就是这个原因。刷题阶段当然不是所有地方的性能都很敏感但“带注释的 Java 代码”本来就该说清楚每一处关键选型。4.3 构造题的共性前序/后序定位根中序划分子树构造类题目并不只有“前序 中序”这一种组合还包括“后序 中序”“层序 中序”、二叉搜索树的序列化与恢复以及根据 BST 的特性把字符串转树等。把这些题放在一起复盘会发现它们全都围绕一个核心先找到根再借助根在中序或顺序约束下的位置切分左右区间。不同之处在于如何定位根。前序序列的规律是“第一个元素为根剩下的区间先左后右”而后序序列则是“最后一个元素为根剩下的区间先左后右”。一旦定位到根总能用某种中序信息如果有提供或者 BST 的大小关系来切分区间。多做几道构造题以后会慢慢形成条件反射看到“某个序列符合顺序特征”第一反应不是去还原整棵树而是去找“根在哪左边界和右边界如何确定”。5. 二叉搜索树与 AVL从“能用”到“知道为什么能用”5.1 BST 的中序有序性质验证、查询与区间问题二叉搜索树BST的结构定义很简单对任意节点左子树所有节点值都小于当前节点右子树所有节点值都大于当前节点。这个定义带来的最大好处是中序遍历 BST 会得到一个严格递增的序列。因为这个性质很多与“顺序”“第 K 大”“区间范围”相关的题目都会考虑先做中序遍历再进行处理。验证一棵树是否为 BST 是基础中的基础。最容易犯的错误是只比较当前节点和左右孩子的大小关系比如觉得“只要 root.left.val root.val 且 root.right.val root.val 就行”。这个判断漏掉了更深层次的要求左子树中所有节点都必须小于当前节点而不只是直接左孩子。解决这个问题通常有两种思路第一种是中序遍历后检查得到的结果是否严格递增第二种是递归时给每棵子树限定一个上下界。第二种写法更通用也更能体现 BST 中“区间约束”的思想。public boolean isValidBST(TreeNode root) { return valid(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean valid(TreeNode node, long lower, long upper) { if (node null) { return true; } // 节点的值必须落在 (lower, upper) 开区间内 if (node.val lower || node.val upper) { return false; } return valid(node.left, lower, node.val) valid(node.right, node.val, upper); }为什么要用Long.MIN_VALUE而不用Integer.MIN_VALUE因为题目测试用例可能正好把 Integer 的最小值或最大值作为二叉树节点的值。如果初始上下界直接用了 Integer 的边界恰好节点值等于边界值时和的判断会直接误杀合法节点。这类问题在实际写代码时极容易忽略一旦样例里有边界值就翻车。多组示例的意义在这里体现得最直接设计测试用例时应当主动把最大值、最小值、重复值都覆盖进去。BST 的插入、查询、删除等操作也都是基于递归缩小搜索范围的思路进行的插入时可以沿着比较路径一路走到空位查询时就近比较大小决定去左还是去右。这些操作的时间复杂度都和树高相关如果 BST 退化成一条链就会退化成 O(n)。5.2 删除节点时Java 引用到底怎么处理BST 的删除操作是很多人觉得棘手的一道题难点在于要分三种情况讨论被删除节点没有左孩子、没有右孩子、同时有左右孩子。没有左右孩子属于空分支直接返回另一侧子树即可比较麻烦的是左右子树都存在的情况。此时必须找到被删除节点的后继右子树中的最小节点用后继节点的值覆盖删除节点的值然后递归去右子树中删除那个后继节点。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) { return root.right; } if (root.right null) { return root.left; } // 寻找右子树中最小的节点作为后继 TreeNode successor root.right; while (successor.left ! null) { successor successor.left; } root.val successor.val; root.right deleteNode(root.right, successor.val); } return root; }很多 Java 初学者在写“删除节点”时潜意识里觉得树操作能像删除数组或链表某个元素那样直接用一个引用把自己替换掉。实际上二叉树的节点之间有单向引用当前递归函数只能通过返回值告诉父节点“我这里已经变成谁了”。所以删除操作的本质是修改父节点对当前节点的引用除非当前节点本身就是根。这点想明白了就能理解为什么这个函数在有子节点时需要返回另一个节点而不是在方法内部做“自我清除”。在刷树题时“引用如何变化”往往比“具体值怎样变化”更重要。我一般看到root.left deleteNode(...)这种递归赋值语句都会刻意停下想一想赋值给左侧相当于父节点把左子树指针指向了新生成的子树根这样递归返回时整棵树的引用链才不会断掉。5.3 AVL 与更高阶的关联先把旋转的动机弄明白网络热词里经常混着“嵌入式 二叉树之avl树”说明 AVL 树不仅是数据结构书上的一章也是很多笔试面试里容易被提到的知识点。但说实话面试里手写完整 AVL 插入并做四种旋转的题目并不算特别高频更常见的考法是“给出一个插入后的局部结构判断该做哪种旋转”。软考等场景中也经常出现 AVL 建树、平衡因子计算这类问题。所以不建议一上来就背左旋右旋代码而是先理解为什么需要旋转。AVL 树的基本判定是每个节点的左右子树高度差绝对值不超过一。当插入或删除导致某个祖先节点平衡因子变成 ±2就必须调整。调整的核心思路是让“不平衡位置附近的三个节点重新排列成一个更均衡的形态”具体是左旋、右旋、左右双旋还是右左双旋取决于哪一侧更深。四种旋转代码并不复杂但如果不理解旋转是在改变父子关系、同时维护 BST 的中序顺序写的时候很容易在子树交接处漏掉一条引用。这一块和树与二叉树专题的刷题关系是延伸关系。建议后面的学习路径可以是先理解 BST 的查找和插入再手动模拟 AVL 在极端序列下自平衡过程最后重新写几遍旋转代码。单纯“看懂了”不会让你真正掌握必须动手在纸上画出每一步的节点引用变化。6. 复杂度分析不写清楚时间空间刷题就缺了最重要的一环6.1 时间复杂度别只写一个 O(n)对每道题给出复杂度分析看似是凑字数实际上是检验自己是否真懂这个算法的试金石。二叉树题目中大量递归函数的复杂度可以用递推式来表达。比如遍历一棵树时每个节点最多被访问常数次因此时间复杂度是 O(n)其中 n 是节点总数。但有些基础题会在递归内部再做一次遍历比如朴素平衡树判断在每个节点都调用一次求高度那就变成了每个节点都要对它下面的子树做一次完整遍历复杂度就是 O(n log n)平衡情况下甚至退化成 O(n²)。如果只笼统地写 O(n)等于没分析。判断一个数是否平衡、求最大路径和这类递归写法也可以从主定理角度理解。以前序遍历为例递归关系大约是 T(n) 2·T(n/2) O(1)理想平衡二叉树下根据主定理得到 O(n)。如果树的形状极端每次只向一侧递归则 T(n) T(n-1) O(1)时间复杂度依然是 O(n)主要的差别体现在空间上。所以在复杂度分析里时间复杂度和树的形状几乎没有变化真正区分度很高的是空间复杂度。6.2 空间复杂度递归栈到底算不算空间很多刷题库对空间复杂度的定义会特别说明递归时系统调用栈占用的空间要计算在内。我第一次学树题时也困惑过递归函数没有额外申请数组为什么空间复杂度不是 O(1)原因在于每次递归调用都会在系统栈上保存当前帧包括局部变量和返回地址在极端单链形态的树下递归深度能达到 n所以空间复杂度是 O(n)。平衡二叉树下递归深度大约是树高 O(log n)空间复杂度自然就是 O(log n)。迭代写法的空间消耗也同样要关注。显式使用栈的时候栈中最大元素个数取决于遍历状态最坏情况下接近 O(n)层序遍历使用队列时队列里最多会容纳某一层的全部节点满二叉树最后一层就有约 n/2 个节点所以空间复杂度同样是 O(n)。很多时候题目允许递归但面试官如果追加一句“能不能不用递归写”你要能回答清楚迭代版的额外空间来源是什么。6.3 常见题型复杂度速查整理笔记时我习惯给每种题型做一张复杂度速查表方便复习时快速回忆。这个习惯让我在复习多道树题时不需要从头再读一遍题解扫一眼表格就能把各种写法的代价串起来。题型常见写法时间复杂度空间复杂度关键说明前序/中序/后序遍历递归O(n)O(h)h 为树高极端链状时为 O(n)前序/中序/后序遍历迭代 栈O(n)O(n)显式栈最坏需要容纳全部节点层序遍历队列O(n)O(n)队列峰值约等于某一层最宽节点数二叉树最大深度后序递归O(n)O(h)每个节点访问一次平衡判断后序归并O(n)O(h)返回 -1 作为失败信号避免重复计算最大路径和后序归并O(n)O(h)全局变量保存整条路径最大值最近公共祖先后序递归O(n)O(h)命中 p/q 后直接向上返回从前序中序构造二叉树哈希表 递归O(n)O(n)哈希表空间 O(n)递归栈 O(h)验证二叉搜索树递归 上下界O(n)O(h)用 Long 边界避免 Int 边界误判BST 删除节点递归 寻找后继O(h)O(h)最坏退化为单链时 O(n)这张表里的空间复杂度都写了 O(h) 而不是固定的 O(log n)是因为树高本身不确定。很多初学者写复杂度时只会写平衡二叉树的情况却忽略了题目从来没有保证“这棵树是平衡的”。严谨一点应该区分“最坏情况”和“平均情况”否则面试反问时会露出破绽。6.4 从复杂度分析倒推优化方向复杂度分析不只是为了在笔记里写上一句话它是帮助你判断一道题是否还有更优解法的罗盘。举个例子如果先序遍历要用递归但是担心递归深度看到 O(h) 的空间复杂度就知道需要改成 Morris 遍历或迭代遍历才能进一步压缩空间如果验证 BST 选择先中序遍历再检查数组是否递增额外空间就是 O(n)改成上下界递归后空间降为 O(h)。这些判断不是靠背模板得来的而是靠“我想要优化某个指标”倒推出的目标。刷树题时比较推荐的做法是每做完一题都问自己三句话最坏情况下树退化成一条链我的代码能跑多深递归栈会不会爆能不能改成迭代版来减少线程栈压力这组问题在真实工程和笔试环境中都可能出现尤其在数据量巨大且不能依赖递归环境的情况下树的高递归深度会成为真正的瓶颈。7. 这一路踩过的坑代码之外的细节同样致命7.1 概念混淆与边界不清树与二叉树最大的概念坑是分不清“二叉树的深度”和“节点的高度”。有些题目里说深度有些说高度如果语义不统一代码容易写乱。从最常见的定义看根节点的深度一般是 0 或 1但不同题库可能从 0 开始也可能从 1 开始写代码前最好先通过示例反推。题目描述中如果给出了多组示例通常可以用示例去确认定义这正是“多组示例附解释”价值所在。另一个容易踩的坑是数组形式的输入里 null 的处理。对于一个类似[1,null,2,3]的输入它根本不是完全二叉树不能用2*i1和2*i2的数组公式去推导某个节点的左右孩子只能按层序遍历顺序重建。不少新手刚接触二叉树题目时会直接拿数组下标当树结构下标结果在构造和遍历的题目里越写越晕。正确做法是把数组先还原成节点对象再在以节点为单位的树上做递归。7.2 Java 代码里的高频运行时错误树类题目使用的是 Java 对象引用所以运行时错误也带有明显特征。最常见的当然是空指针而且往往发生在递归取node.left或node.right之前没有判空。这个问题在层序和迭代写法中尤其突出因为队列中允许存 null但循环体里可能直接访问node.val。应对方法不一定是每个地方都加空判断而是要在设计算法时明确“哪些节点永远不会为 null哪些位置会出现 null”。比如层序遍历弹出队列头时如果是 null就 continue如果节点非空再把左右孩子加入队列这样就能把空指针防御集中在入口处。第二种高频问题是整型溢出。求最大路径和、求 BST 的区间和等题目里初始值如果设为 0 可能无法正确处理全负数数据设为Integer.MIN_VALUE时如果中间做了减法又可能溢出。通常更稳妥的做法是使用 long 参与中间运算或者把初始最大值设置成一个能覆盖所有合法结果的极小值。现实中不少题目的测试用例会专门安排边界数值所以对比较敏感的数据范围一定要多做几组示例验证。第三类问题来自 Java 的“值传递”特性。很多人想在递归函数里更新一个全局最大值直接传一个 int 进去却发现递归返回后 int 没变。这是很经典的 Java 误区。解决办法无非三种用成员变量、用长度为 1 的数组包装、自定义一个可变容器对象。上面最大路径和的代码里我用了int[] max来保存全局答案原理就是数组对象本身引用不变只是内部元素被修改了。如果直接传intJava 是值传递改的只是栈上的副本不会影响外层变量。7.3 短路逻辑、搜索方向与遍历入口树的递归函数如果写了很多 if 分支要特别留意“短路”带来的行为变化。防止空指针常写node null || node.val target这个表达式因为短路逻辑左边为 true 时右边根本不会执行所以不会出现空指针。如果把条件顺序反过来写成node.val target || node null当 node 为 null 时就会立刻崩溃。代码规范课上经常会强调这一点但在递归里往往是最多发的低级 Bug。另一个方向性问题出现在二叉搜索树题目里。BST 每次比较后只能走一个方向搜索但如果是普通二叉树就不能根据数值大小跳过另一边。很多做熟 BST 题的人转到普通二叉树后容易下意识认为“直接比较左右即可”结果漏掉了应有的全面遍历。每次动手前先确认“当前这题里的树是不是 BST”这个判断能避免很多方向性失误。7.4 从“看懂题解”到“独立写出来”的检测方法我整理这套带注释 Java 代码的过程里最意外的一个收获是给代码写注释这件事本身就是最高效的检测工具。如果我发现某一段代码自己怎么也注释不清楚甚至想不出为什么变量要这样命名那就说明我其实并没有真正理解它。这时我会把题目放下第二天重新不看答案写一遍。还写不出来再回去认真读题解写得出来说明这个题才真正属于自己。针对树类题我还总结了一个快速复查的方法把同一道题的递归函数口头翻译成一句话。比如“isBalanced 返回的是当前子树是否平衡”这个一句话能不能说得通决定了代码内部逻辑是否自洽。如果发现一句话里要加很多额外的“但是”“还有”说明递归函数的职责还不明确需要重构。最后的建议是不要把“做的题数”当成绩效指标。刷 10 道只看一遍题解的题不如把 3 道题按完整模板整理好反复看三遍。树与二叉树这个专题尤其适合“少而深”的学习方式因为递归思想差一个环节没有想通下一道题照样会在同一个点卡住。对我而言这套完整结构化的记录帮我养成了稳定的解题习惯先描述题目与示例再定递归函数返回值然后推边界最后写代码和复杂度。现在看到一道新树题我基本能按这套流程快速判断难度和薄弱点在哪里。
