1. 概述
在本篇文章中，我们将学习如何计算二叉树的高度，并通过一个示例来加深理解。
2. 定义
我们先明确一下什么是二叉树中节点的“高度”。
✅ 节点的高度：是指从该节点到其最远叶子节点的路径上边的数量的最大值。如果该节点是叶子节点，那么它的高度为 0。
⚠️ 注意：树的高度指的是根节点的高度，即从根节点到最远叶子节点的边数的最大值。
与高度相对应的概念是“深度”：
✅ 节点的深度：是指从根节点到该节点所经过的边的数量。
⚠️ 一个关键点：整棵树的深度等于其高度，因为树的高度就是根节点到最远叶子的距离。
3. 示例
我们来看一个二叉树的结构图：
3.1 计算节点 C 的高度
节点 C 有两条路径：
- C → E → G（2 条边）
- C → F（1 条边）
最大边数是 2，所以节点 C 的高度是 2。
3.2 计算整棵树的高度
从根节点 A 到叶子节点的路径有：
- A → B → D（2 条边）
- A → C → F（2 条边）
- A → C → E → G（3 条边）
最长路径边数是 3，因此整棵树的高度是 3。
3.3 节点 B 的深度
从根节点 A 到节点 B 只有一条路径：A → B，边数为 1，因此节点 B 的深度是 1。
再次强调：整棵树的深度 = 根节点的高度 = 3
4. 算法实现
我们可以使用递归的方式计算二叉树的高度。基本思路是：
- 如果当前节点为空，返回高度 0；
- 否则分别递归计算左右子树的高度；
- 当前节点的高度为
max(左子树高度, 右子树高度) + 1（加 1 是因为要加上当前节点到子树的那条边）。
下面是 Java 实现代码：
public class BinaryTree {
static class Node {
Node left, right;
Node(Node left, Node right) {
this.left = left;
this.right = right;
}
}
public static int getHeight(Node root) {
if (root == null) {
return 0;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
}
5. 时间复杂度分析
- 最理想情况：树只有一个节点。此时函数只执行一次判断就返回，时间复杂度为
O(1)。 - 一般情况：每个节点都会被访问一次，因此时间复杂度为
O(n)，其中n是节点总数。
✅ 总结：该算法需要遍历所有节点，时间复杂度为 **O(n)**。
6. 小结
我们介绍了二叉树中高度和深度的定义，并通过示例说明了如何计算节点的高度和整棵树的高度。同时给出了一个递归实现的 Java 算法，并对其时间复杂度进行了分析。
💡 小贴士：在实际开发中，如果你遇到树结构相关的算法题，理解“高度”和“深度”的区别是非常关键的，尤其是在处理平衡树（如 AVL 树、红黑树）时。