leetcode/Binary_Tree_Zigzag_Level_Order_Traversal.cpp at master · whodewho/leetcode · GitHub

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

//O(N)
//O(N)

class Solution {
    public:
        vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
            // Start typing your C/C++ solution below
            // DO NOT write int main() function
            vector<vector<int> > res;
            if(root==NULL)return res;
            queue<TreeNode* > queue;
            vector<int> row;
            queue.push(root);
            int pre=1,cur=0,direction=1;
            while(!queue.empty())
            {
                TreeNode *item=queue.front();
                queue.pop();
                row.push_back(item->val);
                pre--;

                if(item->left)queue.push(item->left),cur++;
                if(item->right)queue.push(item->right),cur++;

                if(pre==0)
                {
                    pre=cur;
                    cur=0;
                    if(direction)
                        res.push_back(row);
                    else
                    {
                        reverse(row.begin(),row.end()),res.push_back(row);
                    }
                    row.clear();
                    direction=!direction;
                }
            }
            return res;
        }

        vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
            vector<vector<int> > res;
            if (root == NULL) return res;
            vector<int> row;
            stack<TreeNode*> currS, nextS;
            currS.push(root);
            bool leftToRight = true;
            while (!currS.empty()) {
                while (!currS.empty()) {
                    TreeNode* front = currS.top();
                    currS.pop();
                    row.push_back(front->val);
                    if (leftToRight) {
                        if (front->left) nextS.push(front->left);
                        if (front->right) nextS.push(front->right);
                    }
                    else {
                        if (front->right) nextS.push(front->right);
                        if (front->left) nextS.push(front->left);
                    }
                }
                res.push_back(row);
                row.clear();
                swap(currS, nextS);
                leftToRight = !leftToRight;
            }
            return res;
        }

};