A C++ solution using BFS and stack


  • 0
    G
    class Solution {
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            vector<vector<int>> results;
            if (root == nullptr) return results;
            stack<TreeNode *> st, nst;
            st.push(root);
            int level = 1;
            while (!st.empty()) {
                vector<int> cur_level;
                while (!st.empty()) {
                    TreeNode *node = st.top();
                    st.pop();
                    cur_level.push_back(node -> val);
                    if (level & 1) {
                        if (node -> left) nst.push(node -> left);
                        if (node -> right) nst.push(node -> right);
                    } else {
                        if (node -> right) nst.push(node -> right);
                        if (node -> left) nst.push(node -> left);
                    }
                }
                ++level;
                results.push_back(cur_level);
                swap(st, nst);
            }
            return results;
        }
    };
    

Log in to reply
 

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