LeetCode 筆記：Binary Tree Level Order Traversal（層序遍歷）遞歸與迭代實現

題目大意

二叉樹層序遍歷，返回每層節點值列表（從左到右，層由上到下）。

遞歸實現（按層收集）

遞歸參數攜帶層級 level，確保 result[level-1] 存在後 push_back 節點值。

void dfs(TreeNode* root, int level, vector>& res) {
    if (!root) return;
    if (level > res.size()) res.push_back({});
    res[level-1].push_back(root->val);
    dfs(root->left, level+1, res);
    dfs(root->right, level+1, res);
}

迭代實現（隊列 BFS）

標準 BFS，用隊列存節點，每層處理前記錄隊列大小 sz，循環 sz 次出隊並入隊孩子，收集當層值。

vector> levelOrder(TreeNode* root) {
    vector> res;
    if (!root) return res;
    queue q; q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        vector level;
        while (sz--) {
            TreeNode* n = q.front(); q.pop();
            level.push_back(n->val);
            if (n->left) q.push(n->left);
            if (n->right) q.push(n->right);
        }
        res.push_back(move(level));
    }
    return res;
}

複雜度對比

遞歸：時間 O(n)，空間 O(h) 棧 + O(n) 結果。迭代：時間 O(n)，空間 O(w) 隊列 (w 為最大層寬) + O(n) 結果。迭代無棧溢出風險。