104 二叉樹最大深度

01

題目資訊

題目位址：

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

給定一個二叉樹，找出其最大深度。二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。

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

示例：

給定二叉樹 [3,9,20,null,null,15,7]，
    3
   / \
  9  20
    /  \
   15   7
傳回它的最大深度 3 。
      

02

概述

樹的開篇第一題其實也是比較簡單的，但它的目的是讓我們初步認識樹這樣一個結構。二叉樹每個節點有兩個子節點也就是兩個指針。大概結構如下：

public class TreeNode {
    //節點内容值
    int val;
    //兩個指針
    TreeNode left;
    TreeNode right;
    //構造方法
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
      

03

解法一：深度優先搜尋（DFS）

遞歸的想法，最大深度 = 1 + Max( L0(left) , L0(right))。而每個子樹再找到它最大的深度。下圖就是這樣一個過程，圖中省略一些東西隻畫了一部分了解這樣一個思路就ok

public int maxDepth(TreeNode root) {
    if(root == null) return 0; // 遞歸出口  
    return Math.max(this.maxDepth(root.left), this.maxDepth(root.right)) + 1;
}      

04

解法二：廣度優先搜尋（BFS）

上面是遞歸，這裡是疊代的方式，輸入root節點判斷是否存在存在則深度+1，再判斷下一層節點（輸入1層兩個節點）對一個節點判斷有無子節點，無則出，有則把它的子節點先加進來再出，注意這裡是一個先進先出的關系（排隊）因為是一層一層的周遊完

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int result = 0;
    while (!queue.isEmpty()) {
    //每層每個節點的周遊
        for(int i = quene.size(); i > 0; i--){
            TreeNode node = queue.poll();
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result++;
    }
    return result;
}
      

05

總結