LeetCode/103.binary-tree-zigzag-level-order-traversal.cpp at master · CSUwangj/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
/*
 * @lc app=leetcode id=103 lang=cpp
 *
 * [103] Binary Tree Zigzag Level Order Traversal
 */

// @lc code=start
class Solution {
public:
  vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    if(!root) return {};
    stack<TreeNode*> stackForth;
    stack<TreeNode*> stackBack;
    stackForth.push(root);
    vector<vector<int>> answer;
    while(stackForth.size()) {
      vector<int> result;
      while(stackForth.size()) {
        auto cur = stackForth.top();
        stackForth.pop();
        result.push_back(cur->val);
        if(cur->left) stackBack.push(cur->left);
        if(cur->right) stackBack.push(cur->right);
      }
      answer.push_back(result);
      if(!stackBack.size()) break;
      result.clear();
      while(stackBack.size()) {
        auto cur = stackBack.top();
        stackBack.pop();
        result.push_back(cur->val);
        if(cur->right) stackForth.push(cur->right);
        if(cur->left) stackForth.push(cur->left);
      }
      answer.push_back(result);
    }
    return answer;
  }
};

// Accepted
// 33/33 cases passed (3 ms)
// Your runtime beats 73.66 % of cpp submissions
// Your memory usage beats 48.4 % of cpp submissions (12.2 MB)
// @lc code=end