1. 从“数层数”到“算高度”一个被低估的算法基本功最近在带新人做算法题发现一个挺有意思的现象很多朋友对“求二叉树高度”这个题目第一反应是“这不就是数层数吗”然后随手写个递归就交差了。但真到了面试或者实际项目中稍微变个花样比如要求非递归实现、计算平衡因子、或者结合其他操作如判断平衡二叉树代码就漏洞百出。这让我想起自己刚入门时也觉得这个算法简单到不值一提直到在一次性能调优中因为一个递归求高度的调用被放在了一个O(n²)的循环里直接导致了接口超时才真正重视起这个“基本功”。二叉树的高度或深度定义非常直观从根节点到最远叶子节点的最长路径上的节点数。注意有些教材定义路径的“边数”为高度两者相差1但核心思想一致。求高度之所以重要绝不仅仅是为了回答“这棵树有几层”。它是众多高级算法和数据结构操作的基石判断一棵树是否平衡AVL树的核心、计算树的最小深度、优化树的遍历顺序、乃至在数据库索引如B树中评估查询成本都离不开高效、准确的高度计算。今天我们就抛开“简单”的标签彻底把二叉树求高度这件事聊透从递归到迭代从原理到避坑让你下次遇到它时能写出让面试官眼前一亮的代码。2. 递归解法优雅背后的“栈溢出”陷阱与复杂度真相递归是解决树问题最自然、最符合其定义的方式。二叉树的高度不就是左子树高度和右子树高度的最大值再加1当前节点吗这个“分而治之”的思想清晰无比。2.1 标准递归代码实现与逐行解析我们先来看最经典的实现这里采用节点数为高度的定义即空树高度为0单节点树高度为1。class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val x; } } public class BinaryTreeHeight { public int getHeight(TreeNode root) { // 基准情况如果节点为空高度为0 if (root null) { return 0; } // 递归计算左子树的高度 int leftHeight getHeight(root.left); // 递归计算右子树的高度 int rightHeight getHeight(root.right); // 当前树的高度 左右子树中较大的高度 1 return Math.max(leftHeight, rightHeight) 1; } }这段代码简洁得令人感动但魔鬼藏在细节里。我们逐行拆解基准情况 (if (root null))这是递归的“终点”没有它递归将无限进行下去。对于空树我们定义其高度为0。这个定义是自洽的起点。递归调用 (getHeight(root.left)和getHeight(root.right))这里体现了“后序遍历”Left-Right-Root的思想。我们必须先知道左、右子树的结果才能计算当前节点。程序会沿着左子树一路递归到最左下的叶子节点触底返回后再探索右子树。合并结果 (Math.max(leftHeight, rightHeight) 1)拿到左右子树的高度后当前子树的高度必然是两者中的最大值再加上当前节点自身这一层。注意关于空树高度的定义0还是-1在业界有不同约定。LeetCode等平台通常采用上述“节点数”定义空树为0。若采用“边数”定义空树为-1单节点为0则返回语句应改为Math.max(leftHeight, rightHeight) 1中的1逻辑可能需调整。关键在于整个系统内保持一致。本文统一采用“节点数”定义因为它更直观且与层序遍历的层数概念直接对应。2.2 时间复杂度与空间复杂度深度剖析很多人会脱口而出时间复杂度是O(n)因为每个节点访问一次。这没错但为什么是O(n)我们来严谨推导一下。设树有n个节点。getHeight函数对每个节点恰好执行一次除了空节点但空节点调用是常数时间且与节点数成线性关系。因此时间复杂度是O(n)。空间复杂度才是递归解法的关键也是最容易出错的地方。空间复杂度主要取决于递归调用栈的最大深度也就是树的高度记作h。最好情况树完全平衡高度h ≈ log₂(n)。空间复杂度为O(log n)。最坏情况树退化成一条链表每个节点都只有左孩子或只有右孩子高度h n。此时空间复杂度为O(n)。这意味着如果你面对的是一棵严重倾斜的、拥有10万个节点的“链表树”递归解法将需要约10万层的递归调用栈。这极有可能触发StackOverflowError栈溢出错误尤其是在递归栈空间有限的编程环境如某些嵌入式系统或默认配置的JVM中。这是递归解法最致命的“阿喀琉斯之踵”。2.3 递归解法的典型“坑”与实战心得混淆高度与深度高度是自底向上从叶子到根深度是自顶向下从根到叶子。求高度天然适合后序遍历递归而求某个节点的深度则更适合先序遍历递归。用错遍历顺序逻辑会变得别扭。忽略空指针判断这是最常见的运行时错误。在递归访问root.left或root.right之前必须确保root不为空。我们的代码将判断放在函数开头是最安全的做法。重复计算在一些复杂问题中你可能会无意中多次调用getHeight计算同一棵子树。例如在判断平衡二叉树时一个低效的实现会先调用getHeight算高度再递归判断平衡导致指数级复杂度。解决方案是让getHeight在计算高度的同时返回是否平衡的信息如返回-1表示不平衡这属于“树形DP”的思路。个人心得递归代码写起来爽但交付前一定要问自己我的数据规模有多大树可能有多歪如果存在栈溢出风险迭代解法是必须掌握的备选方案。3. 迭代解法层序遍历BFS——更直观的“数层数”当递归可能带来栈溢出风险时迭代解法就显得更为稳健。求高度最直观的迭代方法就是层序遍历BFS。我们不需要知道子树的结构只需要一层一层地“剥开”这棵树数一数一共剥了多少层。3.1 BFS算法步骤与队列的运用层序遍历使用队列Queue这个数据结构来辅助。初始化如果根节点为空高度为0。否则将根节点放入队列此时高度为1第一层。循环处理每一层获取当前队列的大小levelSize这个数字就是当前层的节点数。将levelSize个节点依次出队并将每个出队节点的非空左、右孩子入队。这一步会将下一层的所有节点加入队列。当前层所有节点处理完毕后意味着我们完整地遍历了一层高度加1。终止当队列为空时说明所有层都已遍历完毕返回累计的高度。3.2 完整代码实现与过程模拟import java.util.LinkedList; import java.util.Queue; public class BinaryTreeHeight { public int getHeightBFS(TreeNode root) { if (root null) { return 0; } int height 0; QueueTreeNode queue new LinkedList(); queue.offer(root); // 根节点入队 while (!queue.isEmpty()) { int levelSize queue.size(); // 当前层的节点数 height; // 处理新的一层高度加1 // 将当前层所有节点出队并将下一层节点入队 for (int i 0; i levelSize; i) { TreeNode currentNode queue.poll(); if (currentNode.left ! null) { queue.offer(currentNode.left); } if (currentNode.right ! null) { queue.offer(currentNode.right); } } } return height; } }让我们模拟一下对一棵简单树(1 (2 4 5) (3))的执行过程初始queue [1],height 0第一轮循环levelSize 1,height变为 1。处理节点1将其孩子2和3入队。queue [2, 3]第二轮循环levelSize 2,height变为 2。处理节点2孩子4,5入队处理节点3无孩子。queue [4, 5]第三轮循环levelSize 2,height变为 3。处理节点4和5均无孩子。queue []循环结束返回height 3。3.3 BFS解法的优势、局限与适用场景优势空间复杂度稳定在最坏情况下完全二叉树队列中最多会存储最后一层的所有节点。最后一层节点数最多约为 n/2因此空间复杂度为 O(n)。但这通常比递归退化情况下的 O(n) 栈空间更能被接受因为队列内存分配在堆上容量远大于栈。直观易懂“数层数”的逻辑与人类思维完全一致代码不易写错。天然适合层相关操作如果你在求高度的同时还需要收集每一层的节点比如做锯齿形遍历BFS是唯一选择。局限与注意点无法利用递归的“副产品”BFS只关心层数在遍历过程中如果你还需要子树的高度信息来做其他计算如平衡因子BFS无法直接提供。代码稍显繁琐相比递归的三行核心代码BFS需要维护队列和循环。levelSize的坑在内部的for循环中一定要先获取queue.size()并存入levelSize而不能在循环条件中直接写i queue.size()。因为循环体内会对队列进行poll和offer操作queue.size()是动态变化的这会导致循环次数错误。适用场景当你确定树可能非常深有栈溢出风险或者问题本身就需要层序遍历时BFS是首选。4. 迭代解法后序遍历DFS模拟——递归思想的迭代翻译有没有一种迭代方法既能避免递归的栈溢出风险又能保留后序遍历“先子节点后父节点”的逻辑顺序呢答案是肯定的我们可以用显式的栈Stack来模拟递归调用的系统栈。这种方法更贴近递归的本质有时在复杂树操作中更有优势。4.1 手动栈模拟递归的核心思想递归的后序遍历顺序是左子树 - 右子树 - 根节点。系统在背后为我们维护了一个调用栈记录了每个函数调用时的状态返回地址、局部变量等。我们可以自己定义一个栈将“待处理的节点”以及“是否需要处理”的状态信息压入栈中。一个常见的技巧是使用一个标记法。我们定义栈中存储的不是简单的TreeNode而是一个包含节点和状态的对象或者用两个栈同步操作。状态指示这个节点是第一次被访问需要先处理其孩子还是孩子都处理完了可以计算高度。4.2 使用“状态标记”的迭代后序遍历实现这里我们使用一个Pair类或Map.Entry来封装节点和状态。状态0表示此节点刚入栈需要先处理其左右孩子状态1表示左右孩子已处理可以访问该节点计算高度。import java.util.Stack; public class BinaryTreeHeight { // 定义一个简单的Pair类封装节点和状态 class StackNode { TreeNode node; int status; // 0: 待处理孩子, 1: 孩子已处理可访问 StackNode(TreeNode n, int s) { node n; status s; } } public int getHeightDFS_Iterative(TreeNode root) { if (root null) return 0; StackStackNode stack new Stack(); stack.push(new StackNode(root, 0)); // 用一个HashMap来记录每个节点的高度避免重复计算 java.util.MapTreeNode, Integer heightMap new java.util.HashMap(); // 初始化叶子节点的高度在访问到时设置 // 后序遍历迭代 while (!stack.isEmpty()) { StackNode current stack.pop(); TreeNode node current.node; if (current.status 0) { // 第一次访问状态改为1重新入栈保证最后处理 stack.push(new StackNode(node, 1)); // 将右孩子、左孩子以状态0入栈栈是LIFO所以先右后左出栈才是先左后右 if (node.right ! null) { stack.push(new StackNode(node.right, 0)); } if (node.left ! null) { stack.push(new StackNode(node.left, 0)); } } else { // 状态为1左右孩子应已处理完或为空 int leftHeight node.left null ? 0 : heightMap.get(node.left); int rightHeight node.right null ? 0 : heightMap.get(node.right); int currentHeight Math.max(leftHeight, rightHeight) 1; heightMap.put(node, currentHeight); // 如果是根节点其高度即为树高 // 但实际上我们需要等循环结束根节点的高度最后被计算出来 } } // 循环结束后根节点的高度已存入map return heightMap.get(root); } }4.3 算法流程拆解与内存使用分析以一棵小树(1 (2) (3))为例根节点1以状态0入栈。stack [(1,0)]弹出(1,0)因其状态为0将其以状态1重新入栈然后右孩子3和左孩子2以状态0入栈。stack [(1,1), (3,0), (2,0)]栈顶在右。弹出(2,0)状态0转为(2,1)入栈其无孩子。stack [(1,1), (3,0), (2,1)]弹出(2,1)状态1计算高度左右孩子空高度1。heightMap: {2-1}弹出(3,0)类似地转为(3,1)入栈。stack [(1,1), (3,1)]弹出(3,1)计算高度1。heightMap: {2-1, 3-1}弹出(1,1)计算高度max(1,1)12。heightMap: {1-2, 2-1, 3-1}。返回2。空间复杂度显式栈的最大深度同样是树的高度h因此空间复杂度为O(h)。与递归相同但使用的是堆上的栈对象通常比系统调用栈更不易溢出。优势它严格模拟了递归的后序过程在需要后序顺序执行复杂操作时非常有用。同时避免了递归的函数调用开销。劣势代码比递归和BFS都复杂需要维护状态和额外的存储如这里的heightMap。在只求高度的问题上显得有些“杀鸡用牛刀”。5. 综合对比与应用场景抉择至此我们掌握了三种主流方法。在实际项目中如何选择我们列个表对比一下特性递归 (Recursive)迭代-BFS (层序)迭代-DFS (显式栈后序)时间复杂度O(n)O(n)O(n)空间复杂度O(h)h为树高最坏O(n)O(w)w为树最大宽度最坏O(n)O(h)h为树高最坏O(n)代码简洁性极简三五行核心代码中等需维护队列和层循环复杂需自定义栈和状态管理直观性符合数学定义思维负担小非常直观“数层数”接近递归但更晦涩栈溢出风险高树深时易发生无低使用堆内存额外优势易于扩展如同时判断平衡天然得到层序结果严格的后序遍历顺序适用场景1. 树深度可控2. 需要子树高度信息3. 快速原型、算法竞赛1. 树可能极深2. 需要层序结果3. 避免递归的环境1. 需要后序迭代且避免递归2. 作为理解递归/迭代转换的教学案例选择建议日常开发与算法面试默认选择优先使用递归。它代码清晰表达了算法的本质。在面试中先写出递归解并主动分析其时间/空间复杂度指出栈溢出风险能体现思维的全面性。已知数据规模大或树结构倾斜使用BFS层序遍历。这是最安全、最通用的迭代方案。特殊需求如果问题明确要求使用迭代且需要后序遍历顺序例如某些内存受限环境禁止递归才考虑显式栈的DFS。6. 高频进阶问题与实战变种掌握了基础解法面试官往往会从以下几个角度进行追问考察你的理解深度和应变能力。6.1 如何判断一棵二叉树是否是平衡二叉树平衡二叉树的定义是任何节点的左右子树高度差不超过1。最直接的想法是写一个getHeight函数然后对每个节点计算左右子树高度差。代码如下public boolean isBalanced(TreeNode root) { if (root null) return true; int leftH getHeight(root.left); int rightH getHeight(root.right); if (Math.abs(leftH - rightH) 1) return false; return isBalanced(root.left) isBalanced(root.right); }但请注意这个算法效率很低。对于每个节点我们都要调用getHeight去计算其子树高度而getHeight本身是O(n)的。这导致总体时间复杂度达到了O(n²)。在节点数为n的链式树上性能无法接受。优化方案自底向上递归我们可以在计算高度的同时判断是否平衡。让getHeight返回一个特殊值如-1来表示子树不平衡否则返回正常高度。这样只需遍历一次。public boolean isBalancedOptimal(TreeNode root) { return balancedHeight(root) ! -1; } private int balancedHeight(TreeNode node) { if (node null) return 0; int leftH balancedHeight(node.left); if (leftH -1) return -1; // 左子树不平衡提前返回 int rightH balancedHeight(node.right); if (rightH -1) return -1; // 右子树不平衡提前返回 if (Math.abs(leftH - rightH) 1) return -1; // 当前节点不平衡 return Math.max(leftH, rightH) 1; // 返回当前节点高度 }这个算法时间复杂度为O(n)每个节点只访问一次空间复杂度为O(h)。6.2 求二叉树的最小深度最小深度是指从根节点到最近叶子节点的路径上的节点数。注意叶子节点指左右孩子都为空的节点。一个常见的错误是直接照搬求高度的代码将max改为min// 错误示例 public int minDepthWrong(TreeNode root) { if (root null) return 0; return Math.min(minDepthWrong(root.left), minDepthWrong(root.right)) 1; }对于树(1 (2))根节点1有一个左孩子2。按照上述代码minDepthWrong(1) min(minDepthWrong(2), minDepthWrong(null)) 1 min(1, 0) 1 1。这错误地返回了1而实际最小深度应该是2根节点1 - 叶子节点2。问题出在当一个节点只有一个孩子时它的最小深度不是由空的那边决定的深度为0而应该由有孩子的那边决定。正确解法需要单独处理节点只有一个孩子的情况。public int minDepth(TreeNode root) { if (root null) return 0; // 如果是叶子节点返回1 if (root.left null root.right null) return 1; int leftDepth minDepth(root.left); int rightDepth minDepth(root.right); // 如果左子树为空最小深度取决于右子树 if (root.left null) return rightDepth 1; // 如果右子树为空最小深度取决于左子树 if (root.right null) return leftDepth 1; // 左右子树都不为空取较小值 return Math.min(leftDepth, rightDepth) 1; }同样这个问题也可以用BFS层序遍历来优雅解决。我们一层一层遍历当第一次遇到一个叶子节点左右孩子都为空时当前的层数就是最小深度。BFS解法在这个问题上通常更优因为它不需要遍历所有节点找到第一个叶子就可以提前结束。6.3 在求高度的同时能否找到最深的叶子节点或路径当然可以。这需要我们在递归过程中不仅传递高度信息还要传递节点信息。我们可以定义一个返回值类包含高度和最深叶子节点或路径。class Result { int height; TreeNode deepestNode; Result(int h, TreeNode n) { height h; deepestNode n; } } public Result getHeightAndDeepestNode(TreeNode root) { if (root null) return new Result(0, null); Result leftResult getHeightAndDeepestNode(root.left); Result rightResult getHeightAndDeepestNode(root.right); // 比较左右子树的高度 if (leftResult.height rightResult.height) { // 左子树更深最深节点在左子树 return new Result(leftResult.height 1, leftResult.deepestNode); } else if (rightResult.height leftResult.height) { // 右子树更深最深节点在右子树 return new Result(rightResult.height 1, rightResult.deepestNode); } else { // 左右子树等高当前节点可能是最深叶子如果它是叶子或者最深节点在任意一边这里约定返回左子树的 // 但更严谨的做法是如果当前节点是叶子它就是最深的之一。我们通常返回第一个找到的。 // 简化处理返回当前节点当它是叶子时或左子树的节点。 TreeNode deepest (root.left null root.right null) ? root : leftResult.deepestNode; return new Result(leftResult.height 1, deepest); } }这个模式非常强大可以解决很多需要从子树“收集”信息并“上传”给父节点的问题是树形动态规划Tree DP的雏形。7. 从理论到实践性能测试与编码注意事项理论分析再好也需要实践验证。我们写一段简单的测试代码来对比一下递归和BFS在不同树形下的实际表现。public class HeightTest { // 生成一棵深度为depth的链式树最坏情况 static TreeNode generateSkewedTree(int depth) { if (depth 0) return null; TreeNode root new TreeNode(1); TreeNode current root; for (int i 2; i depth; i) { current.right new TreeNode(i); // 生成右斜树 current current.right; } return root; } // 生成一棵近似平衡的树 static TreeNode generateBalancedTree(int depth) { if (depth 0) return null; TreeNode root new TreeNode(1); root.left generateBalancedTree(depth - 1); root.right generateBalancedTree(depth - 1); return root; } public static void main(String[] args) { int depth 10000; // 测试深度 System.out.println(测试链式树深度 depth :); TreeNode skewedRoot generateSkewedTree(depth); long start System.currentTimeMillis(); // 递归解法可能会在这里 StackOverflowError // int recHeight new BinaryTreeHeight().getHeight(skewedRoot); long end System.currentTimeMillis(); // System.out.println(递归法耗时: (end - start) ms, 高度: recHeight); start System.currentTimeMillis(); int bfsHeight new BinaryTreeHeight().getHeightBFS(skewedRoot); end System.currentTimeMillis(); System.out.println(BFS法耗时: (end - start) ms, 高度: bfsHeight); System.out.println(\n测试平衡树深度逻辑 15 节点数约 (Math.pow(2, 15)-1) :); TreeNode balancedRoot generateBalancedTree(15); // 深度15的平衡树节点数已超3万 start System.currentTimeMillis(); int recHeight2 new BinaryTreeHeight().getHeight(balancedRoot); end System.currentTimeMillis(); System.out.println(递归法耗时: (end - start) ms, 高度: recHeight2); start System.currentTimeMillis(); int bfsHeight2 new BinaryTreeHeight().getHeightBFS(balancedRoot); end System.currentTimeMillis(); System.out.println(BFS法耗时: (end - start) ms, 高度: bfsHeight2); } }编码中的常见“坑”与最佳实践输入验证公共方法首先要检查根节点是否为null。递归终止条件务必清晰明确。对于树问题if (node null)是最常见的。变量命名使用leftHeight,rightHeight比lh,rh更清晰。方法单一职责getHeight就只负责计算高度。如果需要同时判断平衡应该写一个独立的方法或者像我们之前那样设计一个多功能方法但要在注释中说明。测试用例至少覆盖空树、单节点树、只有左子树/右子树的树、完全二叉树、普通的不平衡树。迭代解法中的循环不变式在BFS的循环中levelSize必须在循环开始前获取这是一个重要的不变式。求二叉树高度这个看似简单的操作贯穿了递归与迭代的思想、时间与空间的权衡、基础与变种的关联。它像一把钥匙能帮你打开理解树形结构、深度优先搜索、广度优先搜索乃至更复杂动态规划的大门。下次再遇到它希望你能会心一笑然后写出那段既正确又高效的代码。