题目描述:()

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? 

解题思路：

递归版：

/** * 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) {        travel(root, 1);                reverse(result.begin(), result.end());                return result;    }        void travel(TreeNode *root, int level) {        if (!root) return;        if (level > result.size()) {            result.push_back(vector
       
        ());        }                result[level - 1].push_back(root->val);        travel(root->left, level + 1);        travel(root->right, level + 1);    }private:    vector
        
         
          > result;};
         
        
       
      
     

迭代版：

1 /** 2  * Definition for a binary tree node. 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     vector
     
      
       > levelOrderBottom(TreeNode* root) {13         vector
       
        
         > result;14         if (!root) return result;15         16         queue
         
           current, next;17         vector
          
            level;18 current.push(root);19 20 while (!current.empty()) {21 while (!current.empty()) {22 TreeNode *tmp = current.front();23 current.pop();24 level.push_back(tmp->val);25 26 if (tmp->left != nullptr) next.push(tmp->left);27 if (tmp->right != nullptr) next.push(tmp->right);28 }29 30 result.push_back(level);31 level.clear();32 swap(current, next);33 }34 35 reverse(result.begin(), result.end());36 37 return result;38 }39 };