C++ yes, you do have a solution that reuses regular level order WITHOUT Reverse


  • 0
    Y

    trick here is to first figure out max height, and in each level, you push to the max_height - cur_height slot, i.e.

      int maxHeight(TreeNode* root){
            if(!root)
                return 0;
            int l =maxHeight(root->left);
            int r =maxHeight(root->right);    
            return  l>r ? l+1 : r+1;
        }
        
        void imp(TreeNode* root, int cur, vector<vector<int>>& res ,int height){
            if(!root)
                return;
            res[height-cur].push_back( root->val);
            imp(root->left, cur+1, res, height);
            imp(root->right, cur+1, res, height);
        }
        vector<vector<int>> levelOrderBottom(TreeNode* root) {
            int h = maxHeight(root);
            vector<vector<int>> res;
            if(h==0)
                return res;
            vector<int> e;
            for(int x= 1 ; x<=h; x++)
                res.push_back(e);
            imp(root, 1 , res, h);
            return res;
        }
    

Log in to reply
 

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