题目描述：

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,#,#,15,7},

3   / \  9  20    /  \   15   7

return its bottom-up level order traversal as:

[  [15,7]  [9,20],  [3],]

解题思路：

1）我的思路：（操作过于复杂）

先将二叉树镜像   3               / \  9  20    /  \   15   7从下到上层序： 15 7 | 9 20 | 3   正常的层序：3 | 3 20 | 15 7    3   / \  20  9 /  \7   15从上到下：  3 | 20 9 | 7 15  与原树从下到上层序（要求解的结果）正好是倒叙，可以将结果存入栈中。使用另一个栈记录每层的节点数。从两个栈中，读取最后结果　　

class Solution {public:    vector
     
      
        > levelOrderBottom(TreeNode *root) {        vector
       
        
          > result;        if(root==nullptr)            return result;        //将二叉树镜像        MirrorBinaryTree(root);        //vector
         
          
            > res; //return res; //层序遍历从左到右，从上到下，存入栈中 stack
           
             treeData,numLevel; queue
            
              pNode; pNode.push(root); TreeNode * curr; int currCount=1,nextCount=0; numLevel.push(currCount); //存第一个root节点，该变量用于存储每层的节点数 while(!pNode.empty()){ //队列不为空的时候 不能直接写 while(pNode) curr = pNode.front(); pNode.pop(); treeData.push(curr->val); //存入当前节点值 currCount--; if(curr->left){ pNode.push(curr->left); nextCount++; } if(curr->right){ pNode.push(curr->right); nextCount++; } if(currCount==0){ if(nextCount!=0) numLevel.push(nextCount); currCount = nextCount; nextCount = 0; } } //从栈中读取结果 vector
             
               row; //int index = 0; while(!numLevel.empty()){ //error:while(numLevel) int num = numLevel.top(); numLevel.pop(); while(num){ num--; row.push_back(treeData.top()); treeData.pop(); } //index++; result.push_back(row); vector
              
                ().swap(row);//清空row中的值 } return result; } void MirrorBinaryTree(TreeNode *root){ //返回值为空，在原树上修改，不要增加新的空间。 //终止条件 if(root==nullptr) return ; if((root->left==nullptr) && (root->right==nullptr)) return ; //交换左右子树 TreeNode *temp = root->left; root->left =root->right; root->right = temp; if(root->left!=nullptr) //递归交换左子树 MirrorBinaryTree(root->left); if(root->right!=nullptr) //递归交换右子树 MirrorBinaryTree(root->right); }};
              
             
            
           
          
         
        
       
      
     

2）广度优先遍历，然后对结果二维数组result的第一个维度做逆转

reverse(res.begin(),res.end());　　//逆转的复杂度是不是很大？

class Solution {public:    vector
     
      
        > levelOrderBottom(TreeNode *root)    {        vector
       
        
         > res;        if(root==nullptr)            return res;        queue
         
           q;        q.push(root);        while(q.size()>0)        {            vector
          
            level; for(int i=0,n=q.size();i
           
            val); if(temp->left) q.push(temp->left); if(temp->right) q.push(temp->right); } res.push_back(level); } reverse(res.begin(),res.end()); //c++ 使用自带函数 return res; }};
           
          
         
        
       
      
     

3) DFS 深度优先遍历　　

　思路很简便：初始化二维数组，存取数字时，从二维数组的第一维度的最大值存储（即从最后一行开始存，然后存倒数第二行）

   初始化时，要知道二维数组一共有多少行，求树的高度即可。

class Solution {public:    int getHeight(TreeNode *root)     {        if(!root) return 0;        return max(getHeight(root->left),getHeight(root->right))+1;     }     vector
     
      
        > levelOrderBottom(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) //定义时取应用，避免复制&res { if(!root) return; res[height].push_back(root->val); dfs(root->left,height-1,res); dfs(root->right,height-1,res); } };　
             
            
           
          
         
        
       
      
     

4） 思路：用递归实现层序遍历

      与正常遍历不同的是，先进行下一层递归，再把当前层的结果保存到res中  

//实现1 res定义为私有变量 class Solution {public:     vector
     
      
        > levelOrderBottom(TreeNode *root)     {             // vector
       
        
         > res;         if(!root) return res;                  queue
         
           currQueue;         currQueue.push(root);         levelOrderBottom(currQueue);         return res;             }     void levelOrderBottom(queue
          
            currQueue){ if(currQueue.empty()) return; int numLevel = currQueue.size(); //层数 vector
           
             row; //读取一层 for(int i=0;i
            
             left) currQueue.push(pNode->left); if(pNode->right) currQueue.push(pNode->right); row.push_back(pNode->val); } levelOrderBottom(currQueue); //先递归后存储，递归到最后一行时，才会开始存储。因此会先存最后一行，满足题目倒叙要求 res.push_back(row); }private: vector
             
              
               > res;};
              
             
            
           
          
         
        
       
      
     

//实现2  res在函数内定义，并传入引用。避免复制引起的操作class Solution {public:     vector
     
      
        > levelOrderBottom(TreeNode *root)     {              vector
       
        
         > res;         if(!root) return res;                  queue
         
           currQueue;         currQueue.push(root);         levelOrderBottom(currQueue,res);         return res;             }     void levelOrderBottom(queue
          
            currQueue,vector
           
            
             >& res){ if(currQueue.empty()) return; int numLevel = currQueue.size(); //层数 vector
             
               row; //读取一层 for(int i=0;i
              
               left) currQueue.push(pNode->left); if(pNode->right) currQueue.push(pNode->right); row.push_back(pNode->val); } levelOrderBottom(currQueue,res); //先递归后存储，递归到最后一行时，才会开始存储。因此会先存最后一行，满足题目倒叙要求 res.push_back(row); }};