二叉树高度计算：从递归到迭代的算法精解与工程实践

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; } }

这段代码简洁得令人感动，但魔鬼藏在细节里。我们逐行拆解：

1. 基准情况 (if (root == null))：这是递归的“终点”，没有它，递归将无限进行下去。对于空树，我们定义其高度为0。这个定义是自洽的起点。
2. 递归调用 (getHeight(root.left)和getHeight(root.right))：这里体现了“后序遍历”（Left-Right-Root）的思想。我们必须先知道左、右子树的结果，才能计算当前节点。程序会沿着左子树一路递归到最左下的叶子节点，触底返回后，再探索右子树。
3. 合并结果 (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 递归解法的典型“坑”与实战心得

1. 混淆高度与深度：高度是自底向上（从叶子到根），深度是自顶向下（从根到叶子）。求高度天然适合后序遍历递归，而求某个节点的深度则更适合先序遍历递归。用错遍历顺序，逻辑会变得别扭。
2. 忽略空指针判断：这是最常见的运行时错误。在递归访问root.left或root.right之前，必须确保root不为空。我们的代码将判断放在函数开头，是最安全的做法。
3. 重复计算：在一些复杂问题中，你可能会无意中多次调用getHeight计算同一棵子树。例如，在判断平衡二叉树时，一个低效的实现会先调用getHeight算高度，再递归判断平衡，导致指数级复杂度。解决方案是让getHeight在计算高度的同时返回是否平衡的信息（如返回-1表示不平衡），这属于“树形DP”的思路。

个人心得：递归代码写起来爽，但交付前一定要问自己：我的数据规模有多大？树可能有多歪？如果存在栈溢出风险，迭代解法是必须掌握的备选方案。

3. 迭代解法：层序遍历（BFS）——更直观的“数层数”

当递归可能带来栈溢出风险时，迭代解法就显得更为稳健。求高度最直观的迭代方法就是层序遍历（BFS）。我们不需要知道子树的结构，只需要一层一层地“剥开”这棵树，数一数一共剥了多少层。

3.1 BFS算法步骤与队列的运用

层序遍历使用队列（Queue）这个数据结构来辅助。

1. 初始化：如果根节点为空，高度为0。否则，将根节点放入队列，此时高度为1（第一层）。
2. 循环处理每一层：
   • 获取当前队列的大小levelSize，这个数字就是当前层的节点数。
   • 将levelSize个节点依次出队，并将每个出队节点的非空左、右孩子入队。这一步会将下一层的所有节点加入队列。
   • 当前层所有节点处理完毕后，意味着我们完整地遍历了一层，高度加1。
3. 终止：当队列为空时，说明所有层都已遍历完毕，返回累计的高度。

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; Queue<TreeNode> 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))的执行过程：

1. 初始：queue = [1],height = 0
2. 第一轮循环：levelSize = 1,height变为 1。处理节点1，将其孩子2和3入队。queue = [2, 3]
3. 第二轮循环：levelSize = 2,height变为 2。处理节点2（孩子4,5入队），处理节点3（无孩子）。queue = [4, 5]
4. 第三轮循环：levelSize = 2,height变为 3。处理节点4和5（均无孩子）。queue = []
5. 循环结束，返回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; Stack<StackNode> stack = new Stack<>(); stack.push(new StackNode(root, 0)); // 用一个HashMap来记录每个节点的高度，避免重复计算 java.util.Map<TreeNode, 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. 根节点1以状态0入栈。stack = [(1,0)]
2. 弹出(1,0)，因其状态为0，将其以状态1重新入栈，然后右孩子3和左孩子2以状态0入栈。stack = [(1,1), (3,0), (2,0)]（栈顶在右）。
3. 弹出(2,0)，状态0，转为(2,1)入栈，其无孩子。stack = [(1,1), (3,0), (2,1)]
4. 弹出(2,1)，状态1，计算高度：左右孩子空，高度=1。heightMap: {2->1}
5. 弹出(3,0)，类似地，转为(3,1)入栈。stack = [(1,1), (3,1)]
6. 弹出(3,1)，计算高度=1。heightMap: {2->1, 3->1}
7. 弹出(1,1)，计算高度：max(1,1)+1=2。heightMap: {1->2, 2->1, 3->1}。返回2。

空间复杂度：显式栈的最大深度同样是树的高度h，因此空间复杂度为O(h)。与递归相同，但使用的是堆上的栈对象，通常比系统调用栈更不易溢出。优势：它严格模拟了递归的后序过程，在需要后序顺序执行复杂操作时非常有用。同时避免了递归的函数调用开销。劣势：代码比递归和BFS都复杂，需要维护状态和额外的存储（如这里的heightMap）。在只求高度的问题上，显得有些“杀鸡用牛刀”。

5. 综合对比与应用场景抉择

至此，我们掌握了三种主流方法。在实际项目中如何选择？我们列个表对比一下：

选择建议：

• 日常开发与算法面试（默认选择）：优先使用递归。它代码清晰，表达了算法的本质。在面试中，先写出递归解，并主动分析其时间/空间复杂度，指出栈溢出风险，能体现思维的全面性。
• 已知数据规模大或树结构倾斜：使用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); } }

编码中的常见“坑”与最佳实践：

1. 输入验证：公共方法首先要检查根节点是否为null。
2. 递归终止条件：务必清晰明确。对于树问题，if (node == null)是最常见的。
3. 变量命名：使用leftHeight,rightHeight比lh,rh更清晰。
4. 方法单一职责：getHeight就只负责计算高度。如果需要同时判断平衡，应该写一个独立的方法，或者像我们之前那样设计一个多功能方法，但要在注释中说明。
5. 测试用例：至少覆盖：空树、单节点树、只有左子树/右子树的树、完全二叉树、普通的不平衡树。
6. 迭代解法中的循环不变式：在BFS的循环中，levelSize必须在循环开始前获取，这是一个重要的不变式。

求二叉树高度这个看似简单的操作，贯穿了递归与迭代的思想、时间与空间的权衡、基础与变种的关联。它像一把钥匙，能帮你打开理解树形结构、深度优先搜索、广度优先搜索乃至更复杂动态规划的大门。下次再遇到它，希望你能会心一笑，然后写出那段既正确又高效的代码。