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

?歡迎訂閱《leetcode》專欄，每日一題，每天進步?

今天又是開心的一天

——leetcode此題熱評

前言

哈嘍，大家好，我是一條，

糊涂演算法，難得糊涂

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;
        }
    }
}