107. Binary Tree Level Order Traversal II

题目

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).For example:Given binary tree [3,9,20,null,null,15,7],    3   / \  9  20    /  \   15   7return its bottom-up level order traversal as:[  [15,7],  [9,20],  [3]]

解析

• 题目虽然思路很清晰，但是查看了方法2,3感觉也吸收了很多思路！

// Binary Tree Level Order Traversal IIclass Solution_107 {public:    //bfs    vector
    
     
      > levelOrderBottom(TreeNode* root) {                vector
      
       
         > vecs;        stack
        
         
          > sta; if (!root) { return vecs; } queue
          
            que; que.push(root); while (!que.empty()) { int size = que.size(); vector
           
             vec; TreeNode* temp; for (int i = 0; i < size;i++) { temp = que.front(); que.pop(); vec.push_back(temp->val); if (temp->left) { que.push(temp->left); } if (temp->right) { que.push(temp->right); } } sta.push(vec); } // reverse(res.begin(),res.end()); while (!sta.empty()) { vector
            
              vec = sta.top(); sta.pop(); vecs.push_back(vec); } return vecs; } // 记录每层的个数；curCount当前层个数，nextCount下一层个节点个数 vector
             
              
               > levelOrderBottom1(TreeNode* root) { int curCount = 0, nextCount = 0, level = 0; vector
               
                
                 > ret; if (!root) return ret; curCount = 1; queue
                 
                   q; q.push(root); ret.push_back(vector
                  
                   (0, curCount)); while (!q.empty()) { if (curCount == 0) { curCount = nextCount; nextCount = 0; level++; ret.push_back(vector
                   
                    (0, curCount)); //初始化下一层vector的大小 } TreeNode *node = q.front(); q.pop(); curCount--; ret[level].push_back(node->val); //在同一层的节点加入 if (node->left) { nextCount++; q.push(node->left); } if (node->right) { nextCount++; q.push(node->right); } } reverse(ret.begin(), ret.end()); return ret; } //dfs int getHeight(TreeNode *root) { if (!root) return 0; return max(getHeight(root->left), getHeight(root->right)) + 1; } vector
                    
                     
                       > levelOrderBottom2(TreeNode *root) { if (!root) return vector
                      
                       
                        >(); vector
                        
                         
                          > res(getHeight(root), vector
                          
                           ()); dfs(root, res.size() - 1, res); return res; } void dfs(TreeNode *root, int height, vector
                           
                            
                             > &res) { if (!root) return; res[height].push_back(root->val); dfs(root->left, height - 1, res); dfs(root->right, height - 1, res); }};
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    

题目来源