Today I have done leetcode's February LeetCoding Challenge with cpp.

February LeetCoding Challenge 19

Description

Binary Tree Zigzag Level Order Traversal

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -100 <= Node.val <= 100

Solution

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)