經(jīng)典Java面試題解析：求二叉樹最大深度

在Java的面試中，求二叉樹的最大深度是一個常見的算法問題。本文將介紹一道經(jīng)典的Java面試題——求二叉樹的最大深度，并提供詳細(xì)的解析和解題思路。

題目

給定一個二叉樹，計算它的最大深度（從根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上的節(jié)點(diǎn)數(shù)）。

解析與解題思路

求二叉樹的最大深度可以使用遞歸或迭代的方式來實現(xiàn)。

1. 遞歸解法：如果二叉樹為空，則返回0。否則，遞歸地求左子樹的最大深度和右子樹的最大深度。最終，返回左子樹最大深度和右子樹最大深度中的較大值加1。
2. 迭代解法（使用層序遍歷）：如果二叉樹為空，則返回0。創(chuàng)建一個隊列，并將根節(jié)點(diǎn)入隊。初始化一個變量maxDepth為0，用于記錄最大深度。當(dāng)隊列不為空時，重復(fù)以下步驟：從隊列中取出當(dāng)前層的所有節(jié)點(diǎn)，并將下一層的節(jié)點(diǎn)加入隊列。更新maxDepth為當(dāng)前層的層數(shù)。最終，返回maxDepth作為結(jié)果。

以下是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) {
        /*
         * 構(gòu)造二叉樹：
         *      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);
    }
}

輸出結(jié)果：

二叉樹的最大深度為：3

結(jié)論

 通過遞歸或迭代的方式，我們可以求解二叉樹的最大深度。掌握了解題思路和實現(xiàn)代碼，我們能夠在面試中更加自信地回答相關(guān)問題。

 學(xué)java，就到java編程獅！