[Leetcode][第104題][JAVA][二叉樹的最大深度][遞歸][BFS]

【問題描述】[簡單]

【解答思路】

1. 遞歸

終止條件/基本情況 root ==null

遞推關系 max(l,r)+1

時間複雜度：O(N) 空間複雜度：O(height)

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


           

2. 廣度優先搜尋 BFS

主要思路：

1. 初始化 root入隊 ，ans記錄層數，root不為空，層數為1
2. 出隊前記錄目前隊列大小size（目前層含有元素個數）
3. 根據獲得size依次出隊 如果左右節點不為空 加入隊列（組成下一層的元素）

4. 根據size周遊完畢後，目前層周遊完畢，層數+1

   時間複雜度：O(N) 空間複雜度：O(1)

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                size--;
            }
            ans++;
        }
        return ans;
    }
}


           

【總結】

1.二叉樹 遞歸 BFS DFS

2.遞歸

在實作遞歸函數之前，有兩件重要的事情需要弄清楚:

遞推關系：一個問題的結果與其子問題的結果之間的關系。

基本情況：不需要進一步的遞歸調用就可以直接計算答案的情況。可了解為遞歸跳出條件。

一旦我們計算出以上兩個元素，再想要實作一個遞歸函數，就隻需要根據遞推關系調用函數本身，直到其抵達基本情況。

3.遞歸模闆套路

由下到上

有上到下

差別

4.相關題目

[Leetcode][第111題][JAVA][BFS][二叉樹的最小深度][BFS][遞歸]

參考連結：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/er-cha-shu-de-zui-da-shen-du-by-leetcode-solution/

遞歸學習資料：https://leetcode-cn.com/circle/article/koSrVI/