107. Binary Tree Level Order Traversal II

Given a binary tree, return thebottom-up level ordertraversal 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/\920/\157


return its bottom-up level order traversal as:

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


解题思路：

此题与Binary Tree Level Order Traversal相似，只是最后的结果有一个反转。

参考http://qiaopeng688.blog.51cto.com/3572484/1834819

代码如下：

/***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNode*left;*TreeNode*right;*TreeNode(intx):val(x),left(NULL),right(NULL){}*};*/classSolution{public:vector<vector<int>>levelOrderBottom(TreeNode*root){vector<vector<int>>result;queue<TreeNode*>current,next;vector<int>level;if(NULL==root)returnresult;current.push(root);while(current.size()){while(current.size()){TreeNode*p;p=current.front();current.pop();level.push_back(p->val);if(p->left)next.push(p->left);if(p->right)next.push(p->right);}result.push_back(level);level.clear();swap(current,next);}reverse(result.begin(),result.end());//相对与BinaryTreeLevelOrderTraversal只加了这一句。reverse()，反转returnresult;}};