Two simple C++ solutions using 1) BFS and reverse 2) BFS and stack


  • 0
    A

    Solution 1: Using BFS and then reversing the list obtained (beats 67%)

    class Solution {
    public:
        vector<vector<int>> levelOrderBottom(TreeNode* root) {
            queue<TreeNode*> q; vector<vector<int>> res;
            
            if(root==NULL) return res;
            q.push(root);
            
            while(!q.empty()){  
                int s = q.size();
                vector<int> temp;
                
                for(int i=0;i<s;i++){
                    TreeNode* node = q.front();                
                    q.pop();
                    
                    if(node->left!=NULL)  q.push(node->left);
                    if(node->right!=NULL) q.push(node->right);        
                    temp.push_back(node->val);
                }
                 res.push_back(temp);
            }  
            reverse(res.begin(),res.end());        
            return res;
        }
    };
    

    Solution 2: Using BFS and a stack to get the reverse level order (beats 16%)

    class Solution {
    public:
        vector<vector<int>> levelOrderBottom(TreeNode* root) {
            queue<TreeNode*> q;
            vector<vector<int>> res;
            stack<vector<int>> st;
            
            if(root==NULL) return res;
            q.push(root);
            
            while(!q.empty()){  
                int s = q.size();
                vector<int> temp;
            
                for(int i=0;i<s;i++){
                    TreeNode* node = q.front();                
                    q.pop();
                    
                    if(node->left!=NULL)  q.push(node->left);
                    if(node->right!=NULL) q.push(node->right);          
                    temp.push_back(node->val);
                }
                 st.push(temp);
            }
            while(!st.empty()){
                res.push_back(st.top()); st.pop();
            }   
            return res;
        }
    };
    

Log in to reply
 

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