Share my iterative and recursive solutions


  • 0
    S
    // dfs + stack iterative solution 
     vector<vector<int> > levelOrder(TreeNode *root) {
        vector<vector<int> > rs;
        if(!root) return rs;
        
        queue<TreeNode *> q;
        q.push(NULL); // a NULL element indicates a new level
        q.push(root);
        
        while(true){
            TreeNode *node = q.front();
            q.pop();
            
            if(!node){
                if(q.empty()) break;
                rs.push_back(vector<int>());
                q.push(NULL);
            }
            else{
                rs.back().push_back(node->val);
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
        }
        
        return rs;
    }
    
    // recursive dfs solution
    vector<vector<int> > levelOrder(TreeNode *root) {
        vector<vector<int> > rs;
        if(!root) return rs;
        dfs_travel(root, rs, 0);
        return rs;
    }
    
    void dfs_travel(TreeNode *root, vector<vector<int>> &vv, int level) {
        if (!root) return;
        if (vv.size() <= level) {
            vector<int> v;
            vv.push_back(v);
        }
        
        vv[level].push_back(root->val);
        dfs_travel(root->left, vv, level + 1);
        dfs_travel(root->right, vv, level + 1);
    }

Log in to reply
 

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