103

Posted on In , Views:

題目:
https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#define MAXN 2005

TreeNode* q[MAXN];

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(root == nullptr) return ans;
        int l = 0, r = 0;
        q[r++] = root;
        bool reverse = false;

        while(l < r){
            int size = r-l;
            vector<int> list;

            // 這邊有一點炫技，迴圈可以展開寫，只是這樣會比較簡潔
            // 也可以用102題的list遍歷法，確認reverse之後再決定是否要反序，再加入ans即可
            for(int i = reverse ? r-1 : l, j = reverse ? -1 : 1, k=0; k<size; i+=j, ++k){
                list.push_back(q[i]->val);
            }

            for(int i=0; i<size; ++i){
                TreeNode* curr = q[l++];
                if(curr->left != nullptr) q[r++] = curr->left;
                if(curr->right != nullptr) q[r++] = curr->right;
            }

            ans.push_back(list);
            reverse = !reverse;
        }
        return ans;
    }
};