4ms C++ BFS Solutions with Explanations


  • 1

    To be honest, I do not know whether this problem is designed to let you use stacks. Anyway, I don't.
    Here are my codes, both BFS and DFS version.

        // BFS 
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            vector<vector<int> > levels;
            if (!root) return levels;
            queue<TreeNode*> toVisit;
            toVisit.push(root);
            int curLevelNodes = 1;
            bool flag = false;
            while (!toVisit.empty()) {
                vector<int> level;
                for (int i = 0; i < curLevelNodes; i++) {
                    TreeNode* node = toVisit.front();
                    toVisit.pop();
                    level.push_back(node -> val);
                    if (node -> left) toVisit.push(node -> left);
                    if (node -> right) toVisit.push(node -> right);
                }
                if (flag) {
                    reverse(level.begin(), level.end());
                    flag = false;
                }
                else flag = true;
                levels.push_back(level);
                curLevelNodes = toVisit.size();
            }
            return levels;
        }
    
        // DFS
        void dfs(TreeNode* node, int curLevel, bool& nextLevel, vector<int>& level) {
            if (!node) return;
            if (curLevel == 1) {
                level.push_back(node -> val);
                if (node -> left || node -> right) nextLevel = true;
            }
            else {
                dfs(node -> left, curLevel - 1, nextLevel, level);
                dfs(node -> right, curLevel - 1, nextLevel, level);
            }
        }
        vector<vector<int> > zigzagLevelOrder(TreeNode* root) {
            vector<vector<int> > levels;
            if (!root) return levels;
            int curLevel = 1;
            bool nextLevel = true, flag = false;
            while (nextLevel) {
                nextLevel = false;
                vector<int> level;
                dfs(root, curLevel++, nextLevel, level);
                if (flag) {
                    reverse(level.begin(), level.end());
                    flag = false;
                } 
                else flag = true;
                levels.push_back(level);
            }
            return levels;
        }
    

    Update

    Thanks to the remind of ljdsoft1, I have rewritten the code to traverse the nodes in ziazag-order instead of simply reversing it. The code is as follows, using two stacks.

    class Solution { 
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            vector<vector<int> > levels;
            if (!root) return levels;
            stack<TreeNode*> curLevel, nextLevel;
            curLevel.push(root);
            bool reversed = false;
            while (!curLevel.empty()) { 
                vector<int> level;
                while (!curLevel.empty()) {
                    TreeNode* node = curLevel.top();
                    curLevel.pop();
                    level.push_back(node -> val);
                    if (reversed) {
                        if (node -> right) nextLevel.push(node -> right);
                        if (node -> left) nextLevel.push(node -> left);
                    }
                    else {
                        if (node -> left) nextLevel.push(node -> left);
                        if (node -> right) nextLevel.push(node -> right);
                    }
                }
                levels.push_back(level);
                swap(curLevel, nextLevel);
                reversed = !reversed; 
            }
            return levels;
        }
    };

  • 0
    L

    I would say you 'cheated'. You didn't traverse in the required order but only do reverse afterwards.


  • 0

    Hi, ljdsoft1. Thank you for your remind. I have updated my solution, adding a new piece of code using two stacks.


Log in to reply
 

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