/*
 * 演算法 / 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);
    }
};