104. Maximum Depth of Binary Tree

Easy
Description

給定一棵二元樹，求其最大深度。最大深度是從根節點到最遠葉節點的最長路徑上的節點數。

Example:

Input: root = [3,9,20,null,null,15,7] Output: 3

Intuition#

樹的最大深度 = 1 + max(左子樹深度, 右子樹深度)。

  • 遞迴地計算左右子樹的深度，取較大值加 1
  • 也可以用 BFS 按層遍歷，計算層數

Approaches#

⭐ 1: Recursive DFS#

  • 概念: 遞迴計算左右子樹深度，回傳較大值 + 1
  • 時間複雜度: O(n)
  • 空間複雜度: 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#

  • 概念: 層序遍歷，每處理一層深度 +1
  • 時間複雜度: O(n)
  • 空間複雜度: 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: 樹的深度/高度計算 — 經典的分治遞迴
  • 關鍵技巧: maxDepth(node) = 1 + max(maxDepth(left), maxDepth(right)) 是許多樹問題的基礎公式