经典Java面试题解析：求二叉树最大深度

在Java的面试中，求二叉树的最大深度是一个常见的算法问题。本文将介绍一道经典的Java面试题——求二叉树的最大深度，并提供详细的解析和解题思路。

题目

给定一个二叉树，计算它的最大深度（从根节点到最远叶子节点的最长路径上的节点数）。

解析与解题思路

求二叉树的最大深度可以使用递归或迭代的方式来实现。

1. 递归解法：如果二叉树为空，则返回0。否则，递归地求左子树的最大深度和右子树的最大深度。最终，返回左子树最大深度和右子树最大深度中的较大值加1。
2. 迭代解法（使用层序遍历）：如果二叉树为空，则返回0。创建一个队列，并将根节点入队。初始化一个变量maxDepth为0，用于记录最大深度。当队列不为空时，重复以下步骤：从队列中取出当前层的所有节点，并将下一层的节点加入队列。更新maxDepth为当前层的层数。最终，返回maxDepth作为结果。

以下是Java代码实例（使用递归解法）：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class MaxDepth {
    public static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int leftDepth = maxDepth(root.left); // 递归地求左子树的最大深度
        int rightDepth = maxDepth(root.right); // 递归地求右子树的最大深度

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

    public static void main(String[] args) {
        /*
         * 构造二叉树：
         *      3
         *     / \
         *    9  20
         *      /  \
         *     15   7
         */
        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 = maxDepth(root);
        System.out.println("二叉树的最大深度为：" + depth);
    }
}

输出结果：

二叉树的最大深度为：3

结论

 通过递归或迭代的方式，我们可以求解二叉树的最大深度。掌握了解题思路和实现代码，我们能够在面试中更加自信地回答相关问题。

 学java，就到java编程狮！