leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0103.cpp (1696B)

      1 class Solution {
      2   public:
      3     vector<vector<int>> zigzagLevelOrder(TreeNode *root) {
      4         if (!root) return {};
      5 
      6         vector<vector<int>> res;
      7         queue<TreeNode *> q;
      8         bool right = true;
      9 
     10         q.push(root);
     11         for (int lvl = 0; !q.empty(); lvl++) {
     12             res.push_back(vector<int>());
     13             for (int t = q.size(); t > 0; t--) {
     14                 TreeNode *root = q.front();
     15                 q.pop();
     16                 res[lvl].push_back(root->val);
     17 
     18                 if (root->left) q.push(root->left);
     19                 if (root->right) q.push(root->right);
     20             }
     21             if (!right) reverse(res[lvl].begin(), res[lvl].end());
     22             right = !right;
     23         }
     24         return res;
     25     }
     26 
     27     vector<vector<int>> zigzagLevelOrder(TreeNode *root) {
     28         if (!root) return {};
     29 
     30         vector<vector<int>> res;
     31         deque<TreeNode *> d;
     32         bool right = true;
     33 
     34         d.push_front(root);
     35         for (int lvl = 0; !d.empty(); lvl++, right = !right) {
     36             res.push_back(vector<int>());
     37             for (int t = d.size(); t > 0; t--) {
     38                 TreeNode *root;
     39                 if (right) {
     40                     root = d.front();
     41                     d.pop_front();
     42                     if (root->left) d.push_back(root->left);
     43                     if (root->right) d.push_back(root->right);
     44                 } else {
     45                     root = d.back();
     46                     d.pop_back();
     47                     if (root->right) d.push_front(root->right);
     48                     if (root->left) d.push_front(root->left);
     49                 }
     50                 res[lvl].push_back(root->val);
     51             }
     52         }
     53         return res;
     54     }
     55 };