二叉樹的深度

---

輸入一棵二叉樹的根結點，求該樹的深度。

從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的深度。

數據范圍

樹中節點數量 $[0,500]$。

樣例

輸入：二叉樹[8, 12, 2, null, null, 6, 4, null, null, null, null]如下圖所示：8/ \12  2/ \6   4輸出：3

---

算法思路

該算法使用遞歸的方式計算二叉樹的最大深度。對于每個節點，其深度等于其左右子樹深度的最大值加1。遞歸的終止條件是遇到空節點，此時深度為0。

• 時間復雜度：O(n)，其中n是二叉樹的節點數。因為需要訪問每個節點一次。
• 空間復雜度：O(h)，其中h是二叉樹的高度。遞歸棧的深度取決于樹的高度，最壞情況下（樹退化為鏈表）為O(n)，平均情況下（平衡二叉樹）為O(log n)。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int treeDepth(TreeNode* root) {// 遞歸終止條件：當前節點為空，深度為0if(!root) return 0;// 遞歸計算左右子樹的深度，取最大值加1作為當前節點的深度return max(treeDepth(root->left), treeDepth(root->right)) + 1;}
};

示例演示

示例1：平衡二叉樹

輸入:3/ \9  20/  \15   7執行過程:
1. treeDepth(3)- treeDepth(9) → 1- treeDepth(20)- treeDepth(15) → 1- treeDepth(7) → 1- max(1, 1) + 1 = 2- max(1, 2) + 1 = 3輸出: 3

示例2：左斜樹

輸入:1/2/3執行過程:
1. treeDepth(1)- treeDepth(2)- treeDepth(3) → 1- treeDepth(NULL) → 0- max(1, 0) + 1 = 2- treeDepth(NULL) → 0- max(2, 0) + 1 = 3輸出: 3

示例3：空樹

輸入: NULL執行過程:
直接返回0輸出: 0

---

擴展

優化1：迭代實現（BFS）

使用廣度優先搜索（BFS）來計算樹的深度，避免遞歸棧的開銷。

int treeDepth(TreeNode* root) {if (!root) return 0;queue<TreeNode*> q;q.push(root);int depth = 0;while (!q.empty()) {int size = q.size();depth++;for (int i = 0; i < size; i++) {TreeNode* node = q.front();q.pop();if (node->left) q.push(node->left);if (node->right) q.push(node->right);}}return depth;
}

特點：

• 空間復雜度：O(n)，最壞情況下隊列中存儲所有葉子節點
• 適合深度較大的樹，避免遞歸棧溢出

優化2：迭代實現（DFS）

使用深度優先搜索（DFS）的迭代版本，模擬遞歸過程。

int treeDepth(TreeNode* root) {if (!root) return 0;stack<pair<TreeNode*, int>> st;st.push({root, 1});int maxDepth = 0;while (!st.empty()) {auto [node, depth] = st.top();st.pop();maxDepth = max(maxDepth, depth);if (node->right) st.push({node->right, depth + 1});if (node->left) st.push({node->left, depth + 1});}return maxDepth;
}

特點：

• 空間復雜度：O(h)，h為樹高
• 更接近遞歸的思路，但使用顯式棧

方法	時間復雜度	空間復雜度	適用場景
原始遞歸	O(n)	O(h)	代碼簡潔，容易理解
BFS迭代	O(n)	O(n)	適合廣度較大的樹
DFS迭代	O(n)	O(h)	更接近遞歸的思路

1. 遞歸方法：代碼簡潔，適合大多數場景，但需要注意遞歸深度限制
2. BFS迭代：適合需要層次遍歷信息的場景，或擔心遞歸棧溢出時
3. DFS迭代：適合需要模擬遞歸過程的場景，空間效率優于BFS