【leetcode刷題】25.二叉樹的最大深度——Java版

前言

哈喽，大家好，我是一條。

糊塗算法，難得糊塗

Question

104. 二叉樹的最大深度

難度：簡單

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

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

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

示例：

給定二叉樹 [3,9,20,null,null,15,7]，

傳回它的最大深度 3 。

Solution

為大家簡答介紹兩個搜尋算法：DFS和BFS

DFS:深度優先搜尋算法，步驟為：

1.遞歸下去

2.回溯上來

顧名思義，深度優先，則是以深度為準則，先一條路走到底，直到達到目标。這裡稱之為遞歸下去。

否則既沒有達到目标又無路可走了，那麼則退回到上一步的狀态，走其他路。這便是回溯上來。

BFD:廣度優先算法

廣度優先搜尋較之深度優先搜尋之不同在于，深度優先搜尋旨在不管有多少條岔路，先一條路走到底，不成功就傳回上一個路口然後就選擇下一條岔路，而廣度優先搜尋旨在面臨一個路口時，把所有的岔路口都記下來，然後選擇其中一個進入，然後将它的分路情況記錄下來，然後再傳回來進入另外一個岔路，并重複這樣的操作。

本題就是基于深度優先搜尋的遞歸：

根節點為空直接傳回

節點為空時說明高度為 0，是以傳回 0；節點不為空時則分别求左右子樹的高度的最大值，同時加1表示目前節點的高度，傳回該數值。

Code

所有leetcode代碼已同步至github

歡迎star

/**
 * @author yitiaoIT
 */

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        } else {
            int left = maxDepth(root.left);
            int right = maxDepth(root.right);
            return Math.max(left, right) + 1;
        }
    }
}      

Result

複雜度分析

• 時間複雜度：O(N)

🌈尋寶

⭐今天是堅持刷題更文的第25/100天

⭐各位的點贊、關注、收藏、評論、訂閱就是一條創作的最大動力

⭐更多算法題歡迎關注專欄《leetcode》

為了回饋各位粉絲，禮尚往來，給大家準備了一條多年積累下來的優質資源，包括 學習視訊、面試資料、珍藏電子書等

怎麼領取請大家自己找，尋寶遊戲現在開始。

找不到可以評論留言，一條就會注意到你。

如果還不行，請私信我。