103. 二叉樹的鋸齒形層序遍歷

前置題目：102. 二叉樹的層序遍歷

思路

在前置題目的基礎上，多加入了一個限制，每一層要跟上一層的方向相反。
假如第一層紀錄左到右，下一層就要紀錄右到左。
用一個變數表示當前方向，然後利用上題的第二種方式稍做修改，就能得到答案。

程式碼

陣列模擬隊列

class Solution {
private:
    const int MX = 2000;
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if(root == nullptr) return {};
        vector<vector<int>> res;
        vector<TreeNode*> q(MX + 1);
        int left = 0, right = 0;
        q[right++] = root;
        bool dir = true; // 這一行是否左到右遍歷
        while(left < right) {
            int size = right - left; // 左閉右開
            vector<int> add;
            for(int i = dir ? left : right - 1, j = dir ? 1 : -1, k = 0; k < size; i += j, ++k) {
                add.push_back(q[i]->val);
            }
            // 能取代上面那一段比較難懂的部分
            // if(dir == true) {
            //     for(int i = left; i < right; ++i) {
            //         add.push_back(q[i]->val);
            //     }
            // }
            // else {
            //     for(int i = right - 1; i >= left; --i) {
            //         add.push_back(q[i]->val);
            //     }
            // }
            dir = !dir;
            res.push_back(add);
            while(size--) {
                TreeNode* cur = q[left++];
                if(cur->left != nullptr) {
                    q[right++] = cur->left;
                }
                if(cur->right != nullptr) {
                    q[right++] = cur->right;
                }
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$