My Neat Solution in C++


  • 25
    F
    vector<vector<int> > levelOrder(TreeNode *root) {
    	vector<vector<int> > retVal;
    
    	levelOrder(root, retVal, 0);
    
    	reverse(retVal.begin(), retVal.end());
    
    	return retVal;
    }
    
    void levelOrder(TreeNode* root, vector<vector<int> > &v, int currLevel) {
    	if (root == NULL) {
    		return;
    	}
    
    	if (v.empty() || currLevel > (v.size() - 1)) {
    		v.push_back(vector<int>());
    	}
    
    	v[currLevel].push_back(root->val);
    
    	levelOrder(root->left, v, currLevel + 1);
    	levelOrder(root->right, v, currLevel + 1);
    }

  • 0
    W

    Using a queue and a stack with iteratition is another way


  • 1
    N

    The following code without reversing too slow (60 ms) because insert operation on vector that too at beginning will be too costly. I wonder if there's any other way that doesn't involve reversing or inserting at front.

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        void levelOrderBottomRecur(TreeNode *root, int level,vector<vector<int> > &result){
            if(root==NULL)
                return;
            
            if(level>=result.size())
                result.insert(result.begin(),vector<int>());
            
            result[result.size()-level-1].push_back(root->val);
            levelOrderBottomRecur(root->left,level+1,result);
            levelOrderBottomRecur(root->right,level+1,result);
        }
        vector<vector<int>> levelOrderBottom(TreeNode* root) {
            vector<vector<int> > result;
            levelOrderBottomRecur(root,0,result);
            return result;
        }
    };

  • 0
    Z

    Don't you think there is something wrong here?
    result[result.size()-level-1].push_back(root->val);


  • 3
    X

    @weijiang2009 8ms

    vector<vector<int>> levelOrderBottom(TreeNode* root) {
    	vector<vector<int>> res;
    	if (!root) {
    		return res;
    	}
    	queue<TreeNode*> t;
    	t.push(root);
    	while (!t.empty()) {
    		vector<int> tn;
    		int cnt = t.size();
    		for (unsigned int i = 0; i < cnt; ++i) {
    			TreeNode *cur = t.front();
    			tn.push_back(cur->val);
    			t.pop();
    			if (cur->left)
    			        t.push(cur->left);
    			if (cur->right)
    				t.push(cur->right);
    		}
    		//do not use insert() here,it cost too much time.
    		//use reverse() insteadly
    		res.push_back(tn);
    	}
    	reverse(res.begin(), res.end());
    	return res;
    }
    

  • 0
    L

    Im having trouble understanding this part :

    if (v.empty() || currLevel > (v.size() - 1)) {
    	v.push_back(vector<int>());
    }
    

    Why do we need it? Wouldnt v always start out as empty and wouldnt the size always be smaller than the level?


  • 0
    J

    @luiscovar I'm stuck here too.Have u figure it out now?


  • 0
    P

    @jaegerstar v is only smaller than level the first time that level is getting populated. After going left, the right node would be stored in the same level. So in that case, you don't need to push_back() an empty vector.


  • 0
    T

    @luiscovar

    A few points:
    (1) v is empty at declaration
    (2) elements of v should be "push_back" when reaching a new deep level ever reached
    (3) at some recursion step, level+1 can be smaller than size of v, for example:

    for the following tree:

    level 0: 1
    level 1: 2 3
    level 2: 4

    when it comes to node 3, node 2,4 have already been visited, size of v is 3. But when it comes to 2, it is the first time reaching level 1, but now v only have 1 element for level 0, so have to push_back another element for this level 2.


  • 0
    L
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
            vector<vector<int>> allres;
            if (root==nullptr)
                return allres;
            stack<vector<int>> s;
            queue<TreeNode*> q;
            q.push(root) ;
            while (!q.empty()) {
                int start=0,end=q.size();
                vector<int> res;
                while (start<end) {
                    TreeNode* current=q.front();
                    q.pop();
                    res.push_back(current->val);
                    if (current->left)
                        q.push(current->left);
                    if (current->right)
                        q.push(current->right);
                    start++;
                }
                s.push(res);
            }
            while (!s.empty()) {
                allres.push_back(s.top());
                s.pop();
            }
            return allres;
        }
    

    my stupid idea


  • 0
    S

    two queue

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<vector<int>> levelOrderBottom(TreeNode* root) {
            vector<vector<int>> ret;
            if(!root)
                return ret;
            queue<TreeNode*> cur_que,next_que;
            vector<int> tem;
            cur_que.push(root);
            while(!cur_que.empty())
            {
                TreeNode* top = cur_que.front();
                tem.push_back(top->val);
                cur_que.pop();
                
                if(top->left) {next_que.push(top->left);}
                if(top->right) {next_que.push(top->right);}
        
                if(cur_que.empty())
                {
                    ret.push_back(tem);
                    tem.clear();
                    cur_que = next_que;
                    next_que = queue<TreeNode*>();
                }
               
                
            }
            reverse(ret.begin(),ret.end());
            return ret;
        }
    };
    

  • 0
    S

    two num, the same as two queue, but half of time(3ms)

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<vector<int>> levelOrderBottom(TreeNode* root) {
            vector<vector<int>> ret;
            if(!root)
                return ret;
            queue<TreeNode*> que;
            vector<int> tem;
            que.push(root);
            int cur_num = 1;
            int next_num = 0;
            while(!que.empty())
            {
                TreeNode* top = que.front();
                tem.push_back(top->val);
                que.pop();cur_num--;
                
                if(top->left) {que.push(top->left);next_num++;}
                if(top->right) {que.push(top->right);next_num++;}
        
                if(cur_num==0)
                {
                    ret.push_back(tem);
                    tem.clear();
                    cur_num = next_num;
                    next_num  =0;
                }
               
                
            }
            reverse(ret.begin(),ret.end());
            return ret;
        }
    };
    

Log in to reply
 

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