App下載

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

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

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

題目

給定一個(gè)二叉樹,計(jì)算它的最大深度(從根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù))。

解析與解題思路

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

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

以下是Java代碼實(shí)例(使用遞歸解法):

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é)論

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

 學(xué)java,就到java編程獅


0 人點(diǎn)贊