App下載

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

萌貨管理員 2023-07-12 09:29:38 瀏覽數(shù) (1304)
反饋

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

題目

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

解析與解題思路

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

  1. 遞歸解法:如果二叉樹為空,則返回0。否則,遞歸地求左子樹的最大深度和右子樹的最大深度。最終,返回左子樹最大深度和右子樹最大深度中的較大值加1。
  2. 迭代解法(使用層序遍歷):如果二叉樹為空,則返回0。創(chuàng)建一個隊列,并將根節(jié)點入隊。初始化一個變量maxDepth為0,用于記錄最大深度。當隊列不為空時,重復(fù)以下步驟:從隊列中取出當前層的所有節(jié)點,并將下一層的節(jié)點加入隊列。更新maxDepth為當前層的層數(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)問題。

 學java,就到java編程獅!


0 人點贊