107. Binary Tree Level Order Traversal II

Total Accepted: 85871 Total Submissions: 247487 Difficulty: Easy

 

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   7

return its bottom-up level order traversal as:

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

 

思路：实质是求自底向上的层序情况。可以见该题的姐妹题题解：

 

代码：

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
          
           
            > v;14         if(root==NULL) return v;15         queue
            
              q;16         q.push(root);17         TreeNode *begin,*end=root,*cur=root;18         while(!q.empty()){19             vector
             
               temp;20 begin=q.front();21 q.pop();22 while(begin!=end){23 temp.push_back(begin->val);24 if(begin->left){25 q.push(begin->left);26 cur=begin->left;27 }28 if(begin->right){29 q.push(begin->right);30 cur=begin->right;31 }32 begin=q.front();33 q.pop();34 }35 temp.push_back(begin->val);36 if(begin->left){37 q.push(begin->left);38 cur=begin->left;39 }40 if(begin->right){41 q.push(begin->right);42 cur=begin->right;43 }44 v.insert(v.begin(),temp); //相较于102题，就是这里变动了45 end=cur;46 }47 return v;48 }49 };