首页 > 代码库 > [leetcode] 7. Binary Tree Level Order Traversal II
[leetcode] 7. Binary Tree Level Order Traversal II
这次相对来讲复杂点，题目如下：
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? > read more on how binary tree is serialized on OJ.
OJ‘s Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where ‘#‘ signifies a path terminator where no node exists below.
Here‘s an example:
1
/
2 3
/
4
5
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".
?
就是按照层数来输出树。思路分为三步，先拿到树的最大层数len，然后再写一个拿指定层的各元素的函数，最后按题目要求写一个返回vector<vector<int>>的函数，里面用一个循环来多次调用之前那个函数，好了，题解如下：
/**
* 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>> temp;
????????int len = MaxDepth(root);
?
?
????????for (int i = len - 1; i >= 0; i--)
????????{
????????????vector<int> level;
????????????getElement(level, 0, i, root);
?
????????????temp.push_back(level);
????????????level.clear();
????????}
?
????????return temp;
?
????}
?
????int MaxDepth(TreeNode *temp)
????{
????????if (temp == NULL)
????????????return 0;
????????else
????????{
????????????int aspros = MaxDepth(temp->left);
????????????int defteros = MaxDepth(temp->right);
????????????return 1 + (aspros>defteros ? aspros : defteros);
????????}
????}
?
????void getElement(vector<int> &level, int count, int len, TreeNode *root)
????{
????????if (root != NULL)
????????{
????????????if (count == len)
????????????{
????????????????level.push_back(root->val);
????????????}
????????????getElement(level, count + 1, len, root->left);
????????????getElement(level, count + 1, len, root->right);
????????}
????}
};
?
因为题目要求是要从底部向上输出，所以在主函数的for循环里用了倒序。
这次的blog用word发布，测试一下。
[leetcode] 7. Binary Tree Level Order Traversal II