Very simple dual stack solution


  • 0
    T
    class Solution {
    public:
      vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if (root == nullptr) {
          return ret;
        }
        vector<int> tmp;
        stack<TreeNode*> st[2];
        int cnt = 0;
        st[cnt & 1].push(root);
        while (!st[0].empty() || !st[1].empty()) {
          int cur = (cnt & 1), next = 1 - cur;
          auto node = st[cur].top();
          st[cur].pop();
          tmp.push_back(node->val);
          if (cur == 1) {
            if (node->right != nullptr) {
              st[next].push(node->right);
            }
            if (node->left != nullptr) {
              st[next].push(node->left);
            }
          } else {
            if (node->left != nullptr) {
              st[next].push(node->left);
            }
            if (node->right != nullptr) {
              st[next].push(node->right);
            }
          }
          if (st[cur].empty()) {
            ++cnt;
            ret.push_back(tmp);
            tmp.clear();
          }
        }
        return ret;
      }
    };
    

Log in to reply
 

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