8ms easy recursive c++ solution


  • 1
    P
    class Solution {
        void Build(TreeNode* root,vector<vector<int> > &lvls,int layer){
            if(!root) return;
            if(layer>=lvls.size()) lvls.push_back(vector<int>{root->val});
            else lvls[layer].push_back(root->val);
            Build(root->left,lvls,layer+1);
            Build(root->right,lvls,layer+1);
            return;
        }
    public:
        vector<vector<int>> levelOrderBottom(TreeNode* root) {
            vector<vector<int> >rst;
            Build(root,rst,0);
            reverse(rst.begin(),rst.end());
            return rst;
        }
    };

  • 1
    A

    Simple Iterative c++ solution

    class Solution {
        public:
            vector<vector<int>> levelOrderBottom(TreeNode* root) {
                
                vector <vector<int> >v;
                TreeNode *tmp=root;
                if(tmp==NULL)
                return v;
                list <TreeNode *>q;
                q.push_back(tmp);
                int i=0;
                while(!q.empty())
                {
                    list <TreeNode *>r;
                    vector <int> v1;
                    while(!q.empty())
                    {
                        TreeNode *x = q.front();
                        q.pop_front();
                        v1.push_back(x->val);
                        if(x->left!=NULL)
                        {
                            r.push_back(x->left);
                        }
                        if(x->right!=NULL)
                        {
                            r.push_back(x->right);
                        }
                    }
                    q=r;
                    v.push_back(v1);
                }
                vector <vector<int> > ans;
                for(i=0;i<v.size();i++)
                ans.push_back(v[v.size()-1-i]);
                return ans;
                
            }
        };

  • 0

    @PKUGoodSpeed I totally have no idea why you guys are getting this so complicated. Using two vectors to imitate the queue process will be much easier and simpler as follows besides the time cost is not reduced a little bit...

    class Solution {
    public:
        vector<vector<int>> levelOrderBottom(TreeNode* root) 
        {
            vector<vector<int>> vv;
            if(!root) return vv;
            vector<TreeNode*> v0, v1;
            v0.push_back(root);
            while(!v0.empty())
            {
                vector<TreeNode*> v1;
                vector<int> v;
                for(int i = 0; i < v0.size(); ++i)
                {
                    v.push_back(v0[i]->val);
                    if(v0[i]->left) v1.push_back(v0[i]->left);
                    if(v0[i]->right) v1.push_back(v0[i]->right);
                }
                v0 = v1;
                vv.push_back(v);
            }
            reverse(vv.begin(), vv.end());
            return vv;
        }
    };
    
    

  • 0

    @PKUGoodSpeed B.T.W. if we use vv.insert(vv.begin(), v) here to avoid reversing process later on, we'll have some trouble in performance which will result in 65ms instead of the current 8ms.


  • 0
    P

    @LHearen good point! I see.


Log in to reply
 

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