Using two stacks.


  • 0
    S
    std::vector<std::vector<int> > zigzagLevelOrder(TreeNode * root) {
      std::vector<std::vector<int> > rst;
      if (!root) return rst;
      std::stack<TreeNode*> stk0;
      std::stack<TreeNode*> stk1;
      stk0.push(root);
      int direction = 0;
      std::stack<TreeNode*> * cs = &stk0;     // current stack
      std::stack<TreeNode*> * ns = &stk1;     // next stack
      while (!cs->empty()) {
          std::vector<int> one_level;
          while (!cs->empty()) {
              TreeNode * tn = cs->top();
              one_level.push_back(tn->val);
              if (direction) {
                  if (TreeNode * right = tn->right) ns->push(right);
                  if (TreeNode * left = tn->left) ns->push(left);
              } else {
                  if (TreeNode * left = tn->left) ns->push(left);
                  if (TreeNode * right = tn->right) ns->push(right);
              }
              cs->pop();
          }
          rst.push_back(one_level);
          direction ^= 1;
          std::swap(cs, ns);
      }
    }

Log in to reply
 

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