C++ Solution, BFS + Stack


  • 0
    C
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (root == nullptr) return result;
        queue<TreeNode*> q;
        q.push(root);
        bool zig = true;
        while (!q.empty()) {
            vector<int> tmp;
            stack<int> s;
            size_t size = q.size();
            for (int i = 0; i < size; ++i) {
                TreeNode* n = q.front(); q.pop();
                zig ? tmp.push_back(n->val) : s.push(n->val);
                if (n->left) q.push(n->left);
                if (n->right) q.push(n->right);
            }
            if (!zig) {
                while (!s.empty()) {
                    tmp.push_back(s.top());
                    s.pop();
                }
            }
            result.emplace_back(move(tmp));
            zig = !zig;
        }
        return vector<vector<int>>(result);
    }

Log in to reply
 

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