LeetCode 筆記：Binary Tree Zigzag Level Order Traversal（之字形層序遍歷）

題目要求

二叉樹之字形層序遍歷：第一層左→右，第二層右→左，第三層左→右，交替進行。

遞歸實現：標記方向

遞歸參數增加 bool leftToRight，每層遞歸時翻轉。若左→右 push_back，否則 insert(begin(), val) 實現右→左。注意 insert(begin()) 為 O(n)，總時間 O(n²)；可改用雙端隊列或最後反轉優化。

代碼示例

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

vector> zigzagLevelOrder(TreeNode* root) {
    vector> res;
    dfs(root, 1, res, true);
    return res;
}

迭代優化（雙端隊列）

每層用 deque，左→右 push_back，右→左 push_front，最後轉為 vector，單層 O(寬度)，總時間 O(n)。

總結

之字形遍歷核心是控制每層插入方向。遞歸簡潔但插入頭部效率低；迭代雙端隊列更優。面試中說明兩種思路及優化。