C++ solution w/ two stacks


  • 0
    J

    /**

    • Definition for a binary tree node.

    • struct TreeNode {

    • int val;
      
    • TreeNode *left;
      
    • TreeNode *right;
      
    • TreeNode(int x) : val(x), left(NULL), right(NULL) {}
      
    • };
      /
      class Solution {
      public:
      vector<vector<int>> zigzagLevelOrder(TreeNode
      root) {
      vector<vector<int>> ret;
      if (!root) return ret;

       stack<TreeNode*> s1, s2;
       s1.push(root);
       vector<int> level;
       bool right = true;
       
       while (!s1.empty()){
           TreeNode* curr = s1.top();
           s1.pop();
           level.push_back(curr->val);
           
           if (right){
               if (curr->left)  s2.push(curr->left);
               if (curr->right) s2.push(curr->right);
           } else{
               if (curr->right) s2.push(curr->right);                       
               if (curr->left)  s2.push(curr->left);
           }
           
           if (s1.empty()) {
               ret.push_back(level);
               level.clear();
               s1.swap(s2);
               right = !right;
           }
       }
       return ret;
      

      }

    };enter code here


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.