1. 项目概述为什么二叉树的高度如此重要在数据结构的世界里二叉树无疑是最经典、最基础的结构之一。无论是准备技术面试还是在实际项目中处理层级数据比如文件系统目录、组织架构图、决策树模型我们都会频繁地与二叉树打交道。而“求树的高度”这个操作看似简单却像一把万能钥匙能帮你快速评估树的规模、判断树的平衡性甚至是优化后续遍历操作的性能。我见过不少初学者一提到递归就发怵面对求高度这种问题要么写出的代码逻辑混乱要么对递归的调用过程一知半解。今天我们就来彻底拆解这个问题用最详细的步骤和图示让你不仅写出代码更能通透地理解背后的每一个递归细节。这篇文章适合所有正在学习数据结构、备战算法面试或者希望巩固递归思维的朋友。我们会从最基本的定义出发一步步推导到代码实现并深入探讨不同遍历方式的应用最后分享几个实战中容易踩的“坑”。2. 核心思路拆解后序遍历的天然优势求一棵二叉树的高度或深度其定义非常直观从根节点到最远叶子节点的最长路径上的节点数。注意有些教材定义边数我们这里采用更常见的节点数定义高度为1的树只有一个根节点。2.1 为什么是后序遍历要计算整棵树的高度我们必须先知道左子树和右子树各自的高度。因为整棵树的高度等于其左右子树中较高的那个高度再加上根节点自身所占的“1”。这个“先左后右最后根”的计算顺序完美契合了后序遍历Left-Right-Root的访问模式。自底向上的计算过程后序遍历会先递归深入到最底层的叶子节点。叶子节点的左右子树高度均为0那么该叶子节点的高度就是max(0, 0) 1 1。这个结果会返回给其父节点。父节点拿到左右子节点的高度后就能计算出自己的高度再向上返回。这个过程像搭积木一样从底部开始层层向上构建出最终的高度。与先序、中序的对比如果是先序遍历根-左-右访问根节点时我们还不知道子树的高度无法进行计算。中序遍历左-根-右同样如此。因此后序遍历是解决此问题最自然、最直接的递归思路。2.2 递归函数的定义与分解我们定义一个递归函数getHeight(node)它的使命是计算并返回以node为根节点的这棵子树的高度。那么如何计算node这棵树的高度呢我们可以将其分解为三个清晰的步骤计算左子树高度如果node有左孩子那么左子树的高度就是leftHeight getHeight(node.left)。如果没有左孩子可以认为左子树高度为0。计算右子树高度同理rightHeight getHeight(node.right)。合并结果当前node为根的树的高度等于max(leftHeight, rightHeight) 1。这里的1代表当前节点自身。这个分解过程构成了递归的核心。递归的终止条件Base Case也显而易见当node为空null时代表一棵空树其高度定义为0。3. 递归过程超详细逐步推演理论可能有些抽象我们用一个具体的二叉树例子像“单步调试”一样一步步跟踪递归的整个过程。假设我们有如下二叉树A (1) / \ (2) B C (3) / \ (4) D E (5)括号内数字为方便叙述的编号非节点值我们的目标是计算根节点A的高度。步骤1调用 getHeight(A)函数开始执行node为A非空。执行leftHeight getHeight(A.left)即getHeight(B)。这里发生了递归调用当前getHeight(A)的执行被暂停等待getHeight(B)的结果。步骤2调用 getHeight(B)node为B非空。执行leftHeight getHeight(B.left)即getHeight(D)。再次递归getHeight(B)暂停。步骤3调用 getHeight(D)node为D非空。执行leftHeight getHeight(D.left)。D.left为空因此调用getHeight(null)。步骤4调用 getHeight(null)这是终止条件函数直接返回0。步骤5回到 getHeight(D)leftHeight获得了值0。继续执行rightHeight getHeight(D.right)。D.right为空调用getHeight(null)并返回0。现在getHeight(D)计算自身高度height max(0, 0) 1 1。getHeight(D)执行完毕将结果1返回给它的调用者即getHeight(B)。步骤6回到 getHeight(B)getHeight(B)之前暂停在计算leftHeight的地方现在它收到了getHeight(D)返回的1。所以leftHeight 1。继续执行rightHeight getHeight(B.right)即getHeight(E)。再次递归。步骤7调用 getHeight(E)过程与getHeight(D)完全类似。E是叶子节点经过计算后getHeight(E)返回结果1给getHeight(B)。步骤8再次回到 getHeight(B)getHeight(B)收到了rightHeight 1。计算自身高度height max(1, 1) 1 2。getHeight(B)执行完毕将结果2返回给它的调用者即getHeight(A)。步骤9回到 getHeight(A)getHeight(A)之前暂停在计算leftHeight的地方现在leftHeight 2。继续执行rightHeight getHeight(A.right)即getHeight(C)。步骤10调用 getHeight(C)C是叶子节点注意图示C没有孩子。计算过程leftHeight getHeight(null) 0rightHeight getHeight(null) 0 高度 max(0,0)1 1。getHeight(C)返回1给getHeight(A)。步骤11最后回到 getHeight(A)getHeight(A)收到了rightHeight 1。计算最终高度height max(2, 1) 1 3。getHeight(A)执行完毕返回最终结果3。通过这样一步步的推演你可以清晰地看到递归调用栈是如何一层层深入递又如何带着计算结果一层层返回归的。整棵树的高度3对应从根节点A到叶子节点D或E的路径A-B-D 或 A-B-E路径上的节点数正好是3个。4. 代码实现与逐行解析理解了递归过程代码实现就水到渠成了。这里提供 Java 版本的实现并附上详细注释。// 定义二叉树节点类 class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val x; } } public class BinaryTreeHeight { /** * 计算二叉树的高度深度 * param root 二叉树的根节点 * return 树的高度 */ public int getHeight(TreeNode root) { // 1. 递归终止条件如果当前节点为空代表空树高度为0 if (root null) { return 0; } // 2. 递归计算左子树的高度 // 这一行代码会触发一系列递归调用直到遇到左子树的所有叶子节点 int leftHeight getHeight(root.left); // 3. 递归计算右子树的高度 // 同样深入右子树进行计算 int rightHeight getHeight(root.right); // 4. 合并结果当前树的高度 左右子树中较高的高度 1 (当前节点) // Math.max() 函数用于取两者中的最大值 int currentHeight Math.max(leftHeight, rightHeight) 1; // 5. 将计算结果返回给上一级调用者 return currentHeight; } }关键行解析if (root null) return 0;这是递归的“安全网”确保递归能在叶子节点处正确终止防止无限递归。它也是计算逻辑的起点高度为0。int leftHeight getHeight(root.left);这是递归的“递”过程。程序控制权转移到左子树上我们信任getHeight函数能正确算出左子树的高度。这是一种典型的“分治”思想。Math.max(leftHeight, rightHeight) 1这是递归的“归”过程的核心逻辑。在获得了子问题的解左右子树高度后合并它们得到当前问题的解。返回值每一层递归调用都会将计算出的“局部高度”返回给它的父调用最终汇聚成整棵树的高度。注意递归的“信任”非常重要。在写递归函数时你需要坚信你定义的函数这里是getHeight已经能正确完成它的任务计算子树高度。你只需要关心如何利用它返回的结果来构建当前节点的答案。5. 迭代解法层序遍历的巧妙应用虽然递归解法简洁优雅但理解迭代解法同样重要尤其是在面试中面试官可能要求避免递归担心栈溢出或者考察你对不同遍历方式的掌握。利用层序遍历BFS来求高度是最直观的迭代方法。核心思路树的高度就等于我们进行层序遍历时总共经历的层数。我们使用一个队列在遍历每一层节点时高度加1。import java.util.LinkedList; import java.util.Queue; public class BinaryTreeHeight { public int getHeightIterative(TreeNode root) { // 如果树为空高度为0 if (root null) { return 0; } QueueTreeNode queue new LinkedList(); queue.offer(root); // 将根节点加入队列 int height 0; // 初始化高度 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); } } // 当内层for循环结束时队列中剩下的全是下一层的节点 // while循环继续开始处理下一层 } return height; } }算法步骤解析初始化队列和高度计数器。将根节点入队。当队列不为空时说明还有层未遍历 a. 获取当前队列的大小levelSize这个大小就是当前层的节点总数。 b. 高度height加 1。 c. 用一个for循环精确地只处理levelSize个节点即当前层。对每个节点将其左右非空子节点入队。这个操作保证了下一层的节点被加入队列。循环结束后height即为树的高度。递归 vs 迭代对比递归代码简洁思维上更符合问题定义分治但存在函数调用栈开销对于极度不平衡的树如链状树可能导致栈溢出。迭代BFS没有栈溢出风险空间复杂度取决于队列中最多存储的节点数最宽的那一层。思维上更贴近“一层层测量”的直观理解。6. 常见问题与深度剖析在实际编码和面试中以下几个问题是高频考点和易错点。6.1 空树和单节点树的高度是多少这是一个经典的边界条件问题。根据我们之前的定义空树root null高度为0。这是递归的基准情形必须明确。只有一个根节点的树高度为1。因为从根节点到它自身它也是叶子节点的路径上只有一个节点。有些资料或题目可能采用不同的定义例如高度定义为边数那么单节点树高度为0。关键在于在解题或交流时必须首先明确你采用的定义并在代码注释中说明。我们的代码实现采用的是“节点数”定义。6.2 递归调用栈溢出怎么办对于一棵非常不平衡的二叉树例如每个节点都只有左孩子退化成一个链表如果节点数量n很大比如10万递归深度就会达到n。这可能会超过编程语言默认的调用栈深度限制Java通常约几千到一万导致StackOverflowError。解决方案使用迭代法层序遍历这是最根本的解决方案完全避免了递归调用。尾递归优化遗憾的是我们求高度的递归写法不是尾递归形式因为最后一步是max()计算和1而不是直接返回递归调用结果。主流编译器如Java的HotSpot JVM不会对这种递归进行优化。人工栈模拟递归DFS迭代你可以使用一个显式的Stack来模拟递归过程但这比层序遍历要复杂通常不是解决此问题的最佳选择。因此当担心栈溢出时优先选择迭代的层序遍历法。6.3 如何理解递归函数中的1这个1是初学者最容易迷糊的地方。它代表的是当前节点本身。getHeight(node)计算的是“以node为根的树”的高度这颗树必然包含node这个节点。当我们从左右子树的高度leftHeight和rightHeight中选出最大值后这个最大值只是子树的高度必须加上当前节点才构成整棵以node为根的树的高度。可以把它想象成搭积木左塔高leftHeight右塔高rightHeight。你要在更高的那座塔上面再放上node这块积木。所以新的总高度是max(leftHeight, rightHeight) 1。6.4 这个算法的时间复杂度和空间复杂度是多少时间复杂度O(n)。无论是递归的后序遍历还是迭代的层序遍历每个节点都恰好被访问一次n为树中的节点总数。空间复杂度递归解法O(h)。其中h是树的高度。空间消耗主要在递归调用栈上。在最坏情况链状树下h n空间复杂度为 O(n)在平衡树情况下h log₂n空间复杂度为 O(log n)。迭代解法层序遍历O(w)。其中w是树的最大宽度节点最多的一层的节点数。在最坏情况完全二叉树下最底层宽度约为n/2空间复杂度为 O(n)。7. 实战扩展与技巧掌握了基础的高度计算我们可以看看它的几个典型应用场景和变体问题。7.1 判断二叉树是否为平衡二叉树平衡二叉树的定义是对于树中的任意一个节点其左右子树的高度差不超过1。求高度是解决这个问题的子过程。解题思路在后序遍历计算高度的同时判断左右子树的高度差。如果任何节点的左右子树高度差大于1则整棵树不平衡。public class BalancedTreeCheck { // 这个辅助函数返回-1表示子树不平衡否则返回子树高度 private int checkHeight(TreeNode root) { if (root null) return 0; int leftHeight checkHeight(root.left); if (leftHeight -1) return -1; // 左子树不平衡提前返回 int rightHeight checkHeight(root.right); if (rightHeight -1) return -1; // 右子树不平衡提前返回 // 判断当前节点是否平衡 if (Math.abs(leftHeight - rightHeight) 1) { return -1; } // 返回当前节点的高度 return Math.max(leftHeight, rightHeight) 1; } public boolean isBalanced(TreeNode root) { return checkHeight(root) ! -1; } }技巧这里使用-1作为一个“特殊值”来传递“不平衡”的信号避免了使用额外的全局变量或复杂的返回值结构是一种简洁有效的编码技巧。7.2 求二叉树的最大路径和困难题关联著名的LeetCode 124题“二叉树中的最大路径和”其核心解法也依赖于类似后序遍历的递归。在计算通过某个节点的“贡献值”时需要知道左右子树能提供的最大收益这个过程与计算高度后选择max(left, right)有异曲同工之妙。理解高度计算是攻克这类更复杂树形DP问题的重要基础。7.3 递归调试技巧当递归代码结果不对时不要慌。可以尝试以下方法画图像我们第二部分那样画出一棵小树手动模拟递归过程这是最有效的方法。打印日志在递归函数的入口和返回处打印节点信息和高度。public int getHeightDebug(TreeNode root, int depth) { String indent .repeat(depth); // 根据深度生成缩进 System.out.println(indent 进入: node (rootnull?null:root.val)); if (root null) { System.out.println(indent 返回: 0); return 0; } int left getHeightDebug(root.left, depth1); int right getHeightDebug(root.right, depth1); int result Math.max(left, right) 1; System.out.println(indent 返回: result (leftleft, rightright)); return result; }通过缩进你可以清晰地看到递归的层级和调用顺序。8. 避坑指南与最佳实践根据我多年的经验以下是新手最容易出错的地方混淆高度和深度节点的深度是从根节点到该节点的路径长度根节点深度为0或1。树的高度是所有节点深度的最大值。求高度通常用后序遍历求深度用前序遍历。但在求树高度这个问题里我们用的是后序。忘记处理空指针递归终止条件if (root null) return 0;必须放在函数最前面这是保证递归正确运行的基石。错误理解返回值递归函数getHeight(node)返回的是以node为根的子树的高度而不是从根节点到node的深度。这个概念的清晰区分至关重要。在迭代法中混淆层使用层序遍历时一定要在while循环开始时用levelSize queue.size()固定住当前层的节点数量。如果直接在循环条件里使用i queue.size()由于队列大小在循环内不断变化会导致逻辑错误。过度优化有人可能会想是否可以在递归时传递当前深度参数遇到叶子节点时更新全局最大深度这本质上是将后序遍历改成了带状态的前序遍历虽然也能得出结果但思维不如后序遍历直接且需要额外的全局变量。在面试中首先给出最标准、最易理解的后序解法是更稳妥的选择。最后理解二叉树求高度绝不仅仅是背下一段代码。它是一把钥匙帮你打开理解递归、分治算法和树形结构的大门。多画图多手动模拟把递归调用栈在脑子里“运行”起来当你真正内化了这个过程再遇到更复杂的树问题如最近公共祖先、序列化等时你会发现它们都共享着相似的分析框架和解决逻辑。