C++ 3ms Use queue and stack


  • 0
    K

    Use a queue to traverse all level of tree nodes and use stack to store the values when going right to left.

    class Solution {
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            vector<vector<int>> ans;
            if (root == nullptr) return ans;
            queue<TreeNode*> aq;
            stack<int> as;
            bool flag = false;
            aq.push(root);
            aq.push(nullptr);
            vector<int> tmp;
            while (!aq.empty()) {
                TreeNode* p = aq.front();
                aq.pop();
                if (p == nullptr) {
                    if (!aq.empty()) aq.push(nullptr);
                    if (flag) {
                        while (!as.empty()) {
                            tmp.push_back(as.top());
                            as.pop();
                        }
                    }
                    ans.push_back(tmp);
                    tmp.resize(0);
                    flag = !flag;
                }else{
                    if (p->left) aq.push(p->left);
                    if (p->right) aq.push(p->right);
                    if (flag) {
                        as.push(p->val);
                    }else{
                        tmp.push_back(p->val);
                    }
                }
            }
            return ans;
        }
    };
    

Log in to reply
 

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