Easy C++ BFS solution


  • 0
    H
    class Solution {
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
           queue<TreeNode * > que;
           queue<int> ique;
           vector<vector<int>> ret;
           que.push(root),ique.push(0);
           while(!que.empty())
           {
               int lv = ique.front();ique.pop();
               root = que.front();que.pop();
               if(root)
              {
                   if(ret.size() <= lv)
                       ret.push_back(vector<int>());
                   ret[lv].push_back(root->val);
                   ique.push(lv+1);ique.push(lv+1);
                   que.push(root->left);que.push(root->right);
               }
           }
            for(int i = 0; i < ret.size(); i++)
               if(i&1) reverse(ret[i].begin(),ret[i].end());
           return ret;
       }
    };

  • 0
    A
    /**
    
    • 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>> v1;
      vector<int> c;
      if(root==NULL)
      return v1;
      stack<TreeNode*> s1;
      stack<TreeNode*> s2;

       s1.push(root);
       while(!s1.empty() || !s2.empty())
       {
           while(!s1.empty())
           {
               root=s1.top();
               s1.pop();
               c.push_back(root->val);
               if(root->left)
                       s2.push(root->left);
               if(root->right)
                       s2.push(root->right);
      
            }
            if(c.size()>0)
                v1.push_back(c);
            c.clear();
            while(!s2.empty())
            {
                root=s2.top();
                s2.pop();
                c.push_back(root->val);
                if(root->right)
                    s1.push(root->right);
                if(root->left)
                    s1.push(root->left);
            }
            if(c.size()>0)
                v1.push_back(c);
            c.clear();
        }
        return v1;
    } 
    

    };


Log in to reply
 

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