掌握树的高度计算（Java语言详解版）

为什么需要计算树的高度？

树的高度在很多场景中都有应用，比如：

• 判断一棵树是否平衡（AVL树）；
• 分析算法的时间复杂度；
• 优化数据库索引结构等。

因此，掌握Java树高度的计算方法，是学习高级数据结构的重要一步。

用递归方式计算树的高度

在Java中，我们通常使用递归来实现树高度的计算，因为树本身就是一种递归结构。

首先，我们需要定义一个二叉树节点类：

class TreeNode {    int val;    TreeNode left;    TreeNode right;    TreeNode(int val) {        this.val = val;        this.left = null;        this.right = null;    }}  

接下来，编写计算树高度的方法：

public static int getHeight(TreeNode root) {    // 基础情况：如果节点为空，高度为0    if (root == null) {        return 0;    }        // 递归计算左右子树的高度    int leftHeight = getHeight(root.left);    int rightHeight = getHeight(root.right);        // 当前树的高度 = 1（当前节点） + 左右子树中较大的高度    return 1 + Math.max(leftHeight, rightHeight);}  

完整示例代码

下面是一个完整的可运行示例：

public class TreeHeightExample {    static class TreeNode {        int val;        TreeNode left;        TreeNode right;        TreeNode(int val) {            this.val = val;        }    }    public static int getHeight(TreeNode root) {        if (root == null) return 0;        return 1 + Math.max(getHeight(root.left), getHeight(root.right));    }    public static void main(String[] args) {        // 构建如下树：        //       1        //      / \        //     2   3        //    / \        //   4   5        TreeNode root = new TreeNode(1);        root.left = new TreeNode(2);        root.right = new TreeNode(3);        root.left.left = new TreeNode(4);        root.left.right = new TreeNode(5);        System.out.println("树的高度为: " + getHeight(root)); // 输出：3    }}  

小结

通过本教程，你已经学会了如何使用递归求树高的方法，并理解了树高度的基本概念。这种方法简洁、高效，时间复杂度为 O(n)，其中 n 是树中节点的数量。

记住，树的高度是数据结构教程中的基础内容，掌握它将为你后续学习平衡树、B树、红黑树等打下坚实基础。

现在，快去动手写一写代码，巩固你的理解吧！