給定一棵二元樹，求其最大深度。最大深度是從根節點到最遠葉節點的最長路徑上的節點數。
Example:
Input: root = [3,9,20,null,null,15,7] Output: 3
Intuition
TIP
樹的最大深度 = 1 + max(左子樹深度, 右子樹深度)。
- 遞迴地計算左右子樹的深度，取較大值加 1
- 也可以用 BFS 按層遍歷，計算層數
Approaches
⭐ 1. Recursive DFS — O(n) / O(h)
- Idea: 遞迴計算左右子樹深度，回傳較大值 + 1
- Time:
O(n) - Space:
O(h)，h 為樹高
class Solution {
fun maxDepth(root: TreeNode?): Int {
if (root == null) return 0
return 1 + maxOf(maxDepth(root.left), maxDepth(root.right))
}
}2. Iterative BFS — O(n) / O(n)
- Idea: 層序遍歷，每處理一層深度 +1
- Time:
O(n) - Space:
O(n)
class Solution {
fun maxDepth(root: TreeNode?): Int {
if (root == null) return 0
val queue: ArrayDeque<TreeNode> = ArrayDeque()
queue.add(root)
var depth = 0
while (queue.isNotEmpty()) {
val size = queue.size
for (i in 0 until size) {
val node = queue.removeFirst()
node.left?.let { queue.add(it) }
node.right?.let { queue.add(it) }
}
depth++
}
return depth
}
}🔑 Takeaways
- Pattern: 樹的深度/高度計算 — 經典的分治遞迴
- Key trick:
maxDepth(node) = 1 + max(maxDepth(left), maxDepth(right))是許多樹問題的基礎公式