題⽬描述

輸⼊⼀棵⼆叉樹，求該樹的深度。從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的⼀條路徑，最⻓路徑的⻓度為樹的深度。

示例1
輸⼊：{1,2,3,4,5,#,6,#,#,7}
返回值：4

思路及解答

聲明：這⾥的輸⼊是⼀個數的根節點，也就是從根節點，我們就可以獲取到樹的所有節點，⽽類似數組的表達⽅式 {1,2,3,4,5,#,6,#,#,7} ，則是按照層次來放的。(⽐如這個樹就是4層)

遞歸

第⼀種⽅法⽐較容易想到，對於任意⼀個節點 node ⽽⾔，我要想知道當前 node 節點（包括當前節點）的深度，肯定得求當前節點的左邊節點（設為 left ）的深度 leftDeepth ，以及獲取右節點（設為 right ）的深度 rightDeepth ，然後求兩者最⼤+1（ Max{leftDeepth,rightDeepth}+1 ），就是當前節點的深度。

思路：二叉樹的深度 = max(左子樹深度, 右子樹深度) + 1

⽽遞歸中⽐較重要的⼀點，是結束條件。在這道題中，如果⼀個節點為 null ，就結束，並且當前節點的深度是 0 。代碼超級⽆敵短：

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

以上解法要是看不明白，可以看詳細點的：

public class Solution {
    public int TreeDepth(TreeNode root) {
        // 遞歸終止條件：空節點深度為0
        if (root == null) {
            return 0;
        }
        
        // 遞歸計算左子樹深度
        int leftDepth = maxDepth(root.left);
        // 遞歸計算右子樹深度
        int rightDepth = maxDepth(root.right);
        
        // 當前樹深度 = 左右子樹最大深度 + 1（當前節點）
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

• 時間複雜度：O(n)，需要訪問每個節點一次
• 空間複雜度：O(h)，遞歸棧深度等於樹高，最壞情況（鏈表）為O(n)

迭代遍歷

思路是如果樹的根節點不為空，則將根節點放進隊列中。也就是，每遍歷一層，深度加1，直到遍歷完所有層

設置深度 deep 為0。使⽤ while 循環，只要隊列不為空，則執⾏下⾯操作：

1. 獲取隊列的⼤⼩ size 。
2. 依次取出隊列的前 size 個元素，如果該元素的左邊節點不為空，則將左邊節點放進隊列，如果該元素的右邊節點不為空，則將該元素的右邊節點放進隊列。
3. 層次 deep+1

public class Solution {
    public int TreeDepth(TreeNode root) {
        if (root == null) return 0;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        
        while (!queue.isEmpty()) {
            // 當前層的節點個數
            int levelSize = queue.size();
            
            // 遍歷當前層的所有節點
            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                
                // 將下一層節點加入隊列
                if (currentNode.left != null) {
                    queue.offer(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.offer(currentNode.right);
                }
            }
            
            // 完成一層遍歷，深度加1
            depth++;
        }
        
        return depth;
    }
}

• 時間複雜度為：O(n)，所有的節點需要進⼊隊列，再出隊列
• 空間複雜度：O(n),藉助了額外的隊列空間。