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]]

 

confused what "{1,#,2,3}" means?

 

这道题目，我想了一天= =

题外话：昨天南京突然降温，超级冷，再加之前天晚上失眠，头脑不太清楚，所以，想这道题想了很久，就是想不对。

想不对的时候乱改一通，又浪费时间又懊丧。

今早真的觉得自己就要做不出来了，后来还是在自己的基础上改对了。

 

我用的方法就是层序遍历+逆序。

层序遍历的时候，我用了一个int值来计每层有多少节点，来判断什么时候得到一个vector。什么时候清空。

思考很重要，耐心很重要。

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    vector
     
      
       > levelOrderBottom(TreeNode* root) {        vector
       
        
         > result;        if(root==NULL) return result;        queue
         
           Tree1;        int count=1,thiscount=0;        TreeNode* p;        Tree1.push(root);        vector
          
            vtree; while(!Tree1.empty()){ p=Tree1.front(); vtree.push_back(p->val); count--; Tree1.pop(); if(p->left!=NULL){ Tree1.push(p->left); thiscount++; } if(p->right!=NULL){ Tree1.push(p->right); thiscount++; } if(count==0){ result.push_back(vtree); vtree.clear(); count=thiscount; thiscount=0; } } reverse(result.begin(),result.end()); return result; }};