Java如何實現求二叉樹的最大深度（附程式碼）

這篇文章帶給大家的內容是關於Java如何實現求二元樹的最大深度（附程式碼），有一定的參考價值，有需要的朋友可以參考一下，希望對你有幫助。

給定一個二元樹，找出其最大深度。

二元樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。

說明: 葉子節點是指沒有子節點的節點。

範例：
給定二元樹 [3,9,20,null,null,15,7]，

   3
  / \
 9  20
   /  \
  15   7

返回它的最大深度下 3 返回它。

透過此題掌握樹的運用

問題分析：求二元樹的深度；

#大家可以瀏覽二元樹的基本概念一覽來進一步的理解二元樹；

我們同樣是利用遞歸的方法來解決此題，根結點不為空，我們就遞歸遍歷左子樹和右子樹，看哪一個子樹的層數更多，最後直至遍歷到葉子結點；

運用一條語句技巧性的實作：

return nleft > nright ? nleft 1 : nright 1;

以這棵二元樹為例：

   3   / \  9  20

  15   7
1.此樹非空

2.遞歸遍歷此樹的左子樹：左子樹非空；左子樹的左子樹和右子樹都為空，則都回傳0，進行判斷，0 == 0，這此樹的左子樹這邊返回0 1 = 1；

#3.遞歸遍歷此樹的右子樹：右子樹非空；右子樹的左子樹和右子樹非空；遞歸遍歷右子樹的左子樹和右子樹的右子樹；右子樹的左子樹的左子樹和右子樹為空，返回0 ，右子樹的右子樹的左子樹和右子樹為空，返回0，進行判斷，0 == 0，則此樹的右子樹的左子樹和右子樹返回0 1 = 1 ，進行判斷1 == 1，則此樹的右子樹這邊返回1 1 = 2；

4.比較左子樹和右子樹，1 < 2 ，則此樹回傳2 1 = 3，則此樹的深度即層數就為3.

#其實此方法的主要想法就是：只要遞歸遍歷一直到此樹的葉子結點，最後只要從葉子結點開始一直向根結點回溯並1，結果就是回溯經過的路徑長度1.

public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int val)
        {
            data = val;
        }
    }

    public int maxDepth(TreeNode root)
    {
        if (root == null)
            return 0;

        int nleft = maxDepth(root.left);
        int nright = maxDepth(root.right);

        return nleft > nright ? nleft + 1 : nright + 1;
    }

public static void main(String[] args)
    {
        TreeNode p = new TreeNode(1);
        p.left = new TreeNode(2);
        p.right = new TreeNode(3);
        p.left.left = null;
        p.left.right = null;
        p.right.left = new TreeNode(4);
        p.right.right = new TreeNode(5);

        Tree1 t = new Tree1();
        System.out.println(t.maxDepth(p));
    }

以上是Java如何實現求二叉樹的最大深度（附程式碼）的詳細內容。更多資訊請關注PHP中文網其他相關文章！