Java 实现二叉树最大深度（LeetCode 104）递归算法详解

给定一个二叉树，找出其最大深度。最大深度是从根节点到最远叶节点的最长路径上的节点数。

引言

“二叉树的最大深度” 算法问题是一个关于树结构的问题，涉及树的深度和遍历。解决这个问题需要对树的结构和深度有一定的理解，同时需要找到一种方法来计算树的最大深度。

通过解答这个问题，我们可以提升对树结构和深度的考虑，同时也能拓展对问题求解的能力。

算法思路

为了计算二叉树的最大深度，我们可以使用递归的方法。具体思路如下：

1. 如果根节点为 null，表示树为空树，最大深度为 0。
2. 否则，递归计算左子树的最大深度和右子树的最大深度。
3. 最大深度等于左子树最大深度和右子树最大深度的较大值加 1（加 1 是因为需要包括根节点本身）。

代码实现

以下是使用 Java 实现的 “二叉树的最大深度” 算法的示例代码：

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

public class MaximumDepthOfBinaryTree {
    public int maxDepth(TreeNode root) {
        // 如果根节点为 null，返回深度为 0
        if (root == null) {
            return 0;
        }

        // 递归计算左子树和右子树的最大深度，取较大值加 1
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);

        return Math.max(leftDepth, rightDepth) + 1;
    }

    public static void main(String[] args) {
        MaximumDepthOfBinaryTree solution = new MaximumDepthOfBinaryTree();

        // Create a sample binary tree
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        int depth = solution.maxDepth(root);

        System.out.println("Maximum depth of the binary tree: " + depth);
    }
}

算法分析

• 时间复杂度：对于每个节点，我们只需访问一次，所以时间复杂度为 O(n)，其中 n 是节点的数量。
• 空间复杂度：递归栈的深度为树的高度，所以空间复杂度为 O(h)，其中 h 是树的高度。

示例和测试

假设给定一个二叉树如下：

    3
   / \
  9  20
    /  \
   15   7

根据算法，计算二叉树的最大深度，结果为 3（根节点到最远叶节点的最长路径是 3）。

我们可以使用以下代码进行测试：

public class Main {
    public static void main(String[] args) {
        MaximumDepthOfBinaryTree solution = new MaximumDepthOfBinaryTree();

        // Create a sample binary tree
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        int depth = solution.maxDepth(root);

        System.out.println("Maximum depth of the binary tree: " + depth);
    }
}

总结

“二叉树的最大深度” 算法题要求计算树的最大深度，是一个关于树结构和深度的问题。

通过实现这个算法，我们可以提升对树结构和深度的考虑，同时也能拓展对问题求解的能力。这个问题利用递归的思路，计算左子树和右子树的最大深度，然后取较大值加 1 即可。更多算法题解和 Java 面试干货，欢迎访问云栈社区。