104. Maximum Depth of Binary Tree

題目 / Problem

中文： 給定一棵二元樹的根節點 root，回傳它的最大深度。二元樹的最大深度是指從根節點沿著最長的一條路徑，一直走到最遠的葉節點時，所經過的節點數量。

English: Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Constraints / 限制： - 節點數量在 [0, 10^4] 範圍內（可能是空樹）。The number of nodes is in the range [0, 10^4] (the tree may be empty). - -100 <= Node.val <= 100

Worked example / 範例：

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

        3          <- 第 1 層 / level 1
       / \
      9  20        <- 第 2 層 / level 2
         / \
        15  7      <- 第 3 層 / level 3

最長路徑是 3 -> 20 -> 15（或 3 -> 20 -> 7），經過 3 個節點，所以深度是 3。 The longest path 3 -> 20 -> 15 passes through 3 nodes, so the depth is 3.

名詞解釋 / Glossary

• 二元樹 / Binary tree： 一種由節點組成的資料結構，每個節點最多有兩個子節點，分別稱為「左子節點」和「右子節點」。A data structure of nodes where each node has at most two children, called the left and right child.
• 根節點 / Root node： 樹最頂端的節點，是所有路徑的起點。The topmost node of the tree; every path starts here.
• 葉節點 / Leaf node： 沒有任何子節點的節點（左右都是空的）。A node with no children (both left and right are empty / NULL).
• 深度 / Depth： 這裡定義為從根到最遠葉節點所經過的節點數（不是邊數）。Here defined as the number of nodes (not edges) on the longest root-to-leaf path.
• 遞迴 / Recursion： 一個函式呼叫它自己來解決更小的子問題。A function that calls itself to solve smaller sub-problems. 這題非常適合遞迴，因為「整棵樹的深度」可以用「子樹的深度」來定義。
• DFS（深度優先搜尋）/ Depth-First Search： 一種走訪策略，先盡可能往深處走，再回頭。A traversal strategy that goes as deep as possible before backtracking. 我們的遞迴解法本質上就是 DFS。
• NULL 指標 / NULL pointer： 在 C/C++ 中表示「不指向任何東西」的指標，這裡用來代表空的子節點或空樹。A pointer that points to nothing; here it represents an empty child or an empty tree.

思路

這題的核心觀察是：一棵樹的深度可以用它子樹的深度來定義。如果一個節點是空的（NULL），那它的深度就是 0——這是最簡單的情況，也是遞迴的終止條件。如果一個節點不是空的，那麼從它出發的最長路徑，一定是先走進它「比較深的那個子樹」，再加上它自己這一層。換句話說：深度(node) = 1 + max(深度(左子樹), 深度(右子樹))。這個公式為什麼成立？因為最長路徑必然通過左子樹或右子樹其中一邊，我們貪心地選較深的那一邊；而 +1 是把當前節點自己算進去。有人可能會想用暴力法「列出所有從根到葉的路徑再取最長」，但那樣需要額外記錄路徑、程式碼更複雜。遞迴公式優雅地把大問題拆成兩個一模一樣的小問題，每個節點只被拜訪一次，因此非常高效。遞迴會自然地一路往下走到葉節點，碰到 NULL 回傳 0，再一層層往上把答案加回來。

The key insight is that a tree's depth is defined in terms of its subtrees' depths. If a node is empty (NULL), its depth is 0 — this is the simplest case and serves as the recursion's base case. If a node is not empty, the longest path starting from it must go into whichever of its two subtrees is deeper, plus the node itself. So: depth(node) = 1 + max(depth(left), depth(right)). Why does this hold? Any root-to-leaf path must pass through either the left or the right subtree, so we greedily pick the deeper side; the +1 accounts for the current node. You could imagine a brute-force approach that enumerates every root-to-leaf path and takes the longest, but that requires tracking paths and is more error-prone. The recursive formula elegantly splits one big problem into two identical smaller ones, visiting each node exactly once, which is why it's efficient. The recursion naturally walks down to the leaves, returns 0 at each NULL, and adds the answers back up level by level.

逐步走查 / Walkthrough

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

我們追蹤每次 maxDepth(node) 的呼叫如何解析。縮排代表遞迴的深淺 / Indentation shows recursion depth. 每個節點回傳 1 + max(左, 右)。

最外層的 maxDepth(3) 回傳 3，就是答案。The outermost call maxDepth(3) returns 3, the final answer. 注意葉節點（9、15、7）的深度都是 1，因為它們的左右子樹都是 NULL（回傳 0）。

Solution — C

/*
 * 演算法 / Algorithm:
 *   遞迴 DFS。空節點深度為 0；否則深度 = 1 + 較深子樹的深度。
 *   Recursive DFS. An empty node has depth 0; otherwise depth = 1 + the deeper subtree.
 *   每個節點只拜訪一次。Each node is visited exactly once.
 */

// LeetCode 已為我們定義好這個節點結構 / LeetCode predefines this node struct:
// struct TreeNode {
//     int val;                  // 節點的值 / the node's value
//     struct TreeNode *left;    // 指向左子節點的指標 / pointer to left child
//     struct TreeNode *right;   // 指向右子節點的指標 / pointer to right child
// };

// 小工具：回傳兩數中的較大者 / Helper: return the larger of two ints.
static int maxOf(int a, int b) {
    return a > b ? a : b;         // 三元運算子：a>b 成立回傳 a，否則回傳 b / ternary: pick a if a>b else b
}

int maxDepth(struct TreeNode* root) {
    // 終止條件 / Base case:
    // 若指標為 NULL（空樹或走到葉節點下方），深度就是 0。
    // If the pointer is NULL (empty tree, or past a leaf), the depth is 0.
    if (root == NULL) {
        return 0;
    }

    // 遞迴求左子樹的深度 / Recurse into the left subtree.
    // root->left 是「解參考取出 root 指向的結構，再拿它的 left 欄位」
    // root->left means "follow the root pointer, then read its left field".
    int leftDepth = maxDepth(root->left);

    // 遞迴求右子樹的深度 / Recurse into the right subtree.
    int rightDepth = maxDepth(root->right);

    // 較深的那一邊 +1（把當前節點自己算進去）就是此節點的深度。
    // The deeper side plus 1 (counting this node itself) is this node's depth.
    return 1 + maxOf(leftDepth, rightDepth);
}

Solution — C++

/*
 * 演算法 / Algorithm:
 *   遞迴 DFS。空節點回傳 0；否則回傳 1 + max(左子樹深度, 右子樹深度)。
 *   Recursive DFS. Return 0 for a null node; otherwise 1 + max(left depth, right depth).
 *   時間 O(n)，每個節點只走一次。Time O(n): each node visited once.
 */

// LeetCode 預先定義的節點結構 / LeetCode's predefined node struct:
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
// };

class Solution {
public:
    int maxDepth(TreeNode* root) {
        // 終止條件：空節點深度為 0。
        // Base case: a null node has depth 0.
        if (root == nullptr) {   // C++ 用 nullptr 表示空指標 / nullptr is C++'s null pointer literal
            return 0;
        }

        // 遞迴計算左、右子樹的深度。
        // Recursively compute the depth of each subtree.
        int leftDepth  = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);

        // std::max 回傳兩者中較大值（來自 <algorithm>，LeetCode 已引入）。
        // std::max returns the larger of the two (from <algorithm>, already included by LeetCode).
        // +1 把當前節點算進去 / +1 counts the current node itself.
        return 1 + std::max(leftDepth, rightDepth);
    }
};

複雜度 / Complexity

• Time: O(n) — 其中 n 是樹的節點總數。每個節點恰好被 maxDepth 呼叫一次，每次只做常數量的工作（比大小、加法）。n is the total number of nodes; each node triggers exactly one call doing constant work, so the total is linear.
• Space: O(h) — 其中 h 是樹的高度，來自遞迴呼叫堆疊（call stack）的深度。最壞情況是「歪斜樹」（每個節點只有一個子節點），此時 h = n，空間為 O(n)；平衡樹則約為 O(log n)。The space comes from the recursion call stack, which is as deep as the tree is tall. Worst case (a skewed tree) is O(n); a balanced tree is about O(log n).

Pitfalls & Edge Cases

• 空樹 / Empty tree (root == NULL)： 必須先檢查 NULL 再存取 root->left，否則會解參考空指標導致崩潰。程式的第一行 if (root == NULL) 正是為此。You must check for NULL before touching root->left, or you dereference a null pointer and crash; the base case handles this and correctly returns 0.
• 深度是「節點數」不是「邊數」/ Depth counts nodes, not edges： 有些「樹高」定義用邊數（會少 1）。這裡的 +1 與「葉節點深度為 1」符合本題的節點數定義。Some definitions count edges (one less); the +1 and "leaf depth = 1" match this problem's node-count definition.
• 忘記回傳較深的一邊 / Forgetting to take the max： 必須用 max(left, right) 而不是只看某一邊或相加，否則答案會錯。You must take the deeper subtree, not just one side or the sum.
• 極深的樹造成堆疊溢位 / Stack overflow on very deep trees： 節點上限 10^4，遞迴深度在合理範圍內、不會溢位；但若面對百萬級的歪斜樹，遞迴可能爆堆疊，那時需改用迭代（顯式 stack 或 BFS）。With up to 10^4 nodes recursion is safe here, but for extremely deep skewed trees an iterative BFS/stack version would be needed.
• 值可以是負數 / Values can be negative (-100 <= val)： 本解法只看結構、不看 val，所以負值完全不影響。This solution never inspects val, so negative values are irrelevant.