Clean C++ BFS / DFS solutions


  • 0

    BFS:

    class Solution {
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
            vector<vector<int>>res;
            if(!root) return res;
            deque<TreeNode*>cur;
            deque<TreeNode*>next;
            cur.push_back(root);
            int level = 0;
            res.push_back(vector<int>());
            while(!cur.empty()){
                TreeNode* node = cur.front();
                cur.pop_front();
                if(node->left) next.push_back(node->left);
                if(node->right) next.push_back(node->right);
                res[level].push_back(node->val);
                if(cur.empty() && !next.empty()){
                    res.push_back(vector<int>());
                    level++;
                    swap(cur, next);
                }
            }
            return res;
        }
    };
    

    DFS:

    class Solution {
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
            vector<vector<int>>res;
            DFS(res, root, 0);
            return res;
        }
        
        void DFS(vector<vector<int>>& res, TreeNode* root, int level){
            if(!root) return;
            if(level == res.size()) res.push_back(vector<int>());
            res[level].push_back(root->val);
            DFS(res, root->left, level + 1);
            DFS(res, root->right, level + 1);
        }
    };
    

Log in to reply
 

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