4ms C++ solution with two stacks


  • 0
    H
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> vv;
        
        stack<TreeNode*> stk1;
        stack<TreeNode*> stk2;
        
        if (root) stk1.push(root);
        bool ordered = true;
        while (!stk1.empty() || !stk2.empty()) {
            vector<int> v;
            if (ordered) {
                while (!stk1.empty()) {
                    TreeNode* n = stk1.top();
                    stk1.pop();
                    if (n) {
                        v.push_back(n->val);
                        if (n->left) stk2.push(n->left);
                        if (n->right) stk2.push(n->right);
                    }
                }
            } else {
                while (!stk2.empty()) {
                    TreeNode* n = stk2.top();
                    stk2.pop();
                    if (n) {
                        v.push_back(n->val);
                        if (n->right) stk1.push(n->right);
                        if (n->left) stk1.push(n->left);
                    }
                }
            }
            ordered = !ordered;
            vv.push_back(v);
        }
        
        return vv;
    }

Log in to reply
 

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