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：
可以在“Binary Tree Level Order Traversal”题目基础上，返回结果时，将结果反转。可以使用reverse(vec.begin(),vec.end())语句，也可以使用其他重新排列方式。
解题思路2：
和1中的BFS的思路一致，只是将每一层获取到的valLst插入vec的头部，这样就避免了最后再反转。
【★】注意：
由于vector内部数据结构是数组，因此从数组头部插入需要消耗更多的时间复杂度。
实践证明，先按正序填充vector再进行反转（思路1），比直接在头部插入（思路2）需要的时间明显减少。
时间消耗对比：
思路1：
思路2：
思路2代码（BFS）：
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int> > levelOrderBottom(TreeNode *root) {
vector<vector<int> > levelOrderLst;
vector<int> valLst;
queue<TreeNode *> curLevelNodes; if (!root)
return levelOrderLst; curLevelNodes.push(root); while (!curLevelNodes.empty()) {
int len = curLevelNodes.size();
while (len--) {
valLst.push_back(curLevelNodes.front()->val); if (curLevelNodes.front()->left) {
curLevelNodes.push(curLevelNodes.front()->left);
} if (curLevelNodes.front()->right) {
curLevelNodes.push(curLevelNodes.front()->right);
} curLevelNodes.pop();
} levelOrderLst.insert(levelOrderLst.begin(),valLst);
valLst.clear();
} return levelOrderLst;
}
};
附录：
vector