LeetCode 104：Maximum Depth of Binary Tree（二叉樹的最大深度）

一、題目描述

給定一棵二叉樹，找出其最大深度。最大深度是指從根節點到最遠葉子節點的最長路徑上的節點數。

二、解題思路：遞歸 DFS

最大深度 = 1 + max(左子樹深度, 右子樹深度)。空節點深度為 0。

三、代碼實現（Java/C++）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        return dfs(root);
    }

    private int dfs(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(dfs(root.left), dfs(root.right));
    }
}

四、迭代法（BFS 層序遍歷）

用隊列逐層遍歷，計數層數：

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    queue<TreeNode*> q;
    q.push(root);
    int depth = 0;
    while (!q.empty()) {
        int sz = q.size();
        depth++;
        for (int i = 0; i < sz; ++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)
• 空間複雜度：O(H) 遞歸棧 或 O(N) 隊列

本題為二叉樹基礎題，掌握遞歸與迭代兩種寫法。