I*********e
发帖数: 61 | 1 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).
感觉应该用post-order traverse,但是不知道怎么样才能从最低的一个Level开始
return。
多谢指教。 |
q****m
发帖数: 177 | 2 recursive ?
nodes
【在 I*********e 的大作中提到】
: 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).
: 感觉应该用post-order traverse,但是不知道怎么样才能从最低的一个Level开始
: return。
: 多谢指教。
|
p*****2
发帖数: 21240 | |
C***U
发帖数: 2406 | 4 如果是leetcode那个要求的话 你就从上往下走 然后存的时候倒着存就可以了‘啊
nodes
【在 I*********e 的大作中提到】
: 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).
: 感觉应该用post-order traverse,但是不知道怎么样才能从最低的一个Level开始
: return。
: 多谢指教。
|
l****c
发帖数: 782 | 5 recursion+stack?
1.从上往下读children，输入为root，只要不为空，将children存在vector里面，推入
stack
2.直到输入为空，跳出recursion，
4.读stack？ |
l****c
发帖数: 782 | 6 好像不用recursion也行，就用一个tmp_vector，如果不为空，就继续读vector里面每
个node的children，写入新tmp_vector，新的tmp也加到stack里面，最后读stack。 |
e***s
发帖数: 799 | 7 BFS变形，一个Queue，一个Stack。
root入Queue, 出Queue入Stack， root.Right入Queue， root.Left入Queue......
入队列的时候先右后左，从Stack里出来就是从左往右了
不知道对不对。 |
l****c
发帖数: 782 | 8 你这样可能无法输出example那样的不同高度分组吧
【在 e***s 的大作中提到】
: BFS变形，一个Queue，一个Stack。
: root入Queue, 出Queue入Stack， root.Right入Queue， root.Left入Queue......
: 入队列的时候先右后左，从Stack里出来就是从左往右了
: 不知道对不对。
|
e***s
发帖数: 799 | 9 没看题目不好意思，回头研究一下。
【在 l****c 的大作中提到】
: 你这样可能无法输出example那样的不同高度分组吧
|
I*********e
发帖数: 61 | 10 可以從上往下一行一行的讀，存到一個臨時的vector >,輸出的時候可以
到這輸出這個vector >。不過這恐怕不是題目要求的做法吧？
【在 C***U 的大作中提到】
: 如果是leetcode那个要求的话 你就从上往下走 然后存的时候倒着存就可以了‘啊
:
: nodes
|
|
|
I*********e
发帖数: 61 | |
l****c
发帖数: 782 | 12 vector > levelOrderBottom(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector tmp;
stack> result_stack;
tmp.push_back(root);
while(tmp.size()!=0) {
result_stack.push(tmp);
vector cur = tmp;
tmp.clear();
vector::iterator it;
for (it = cur.begin(); it < cur.end(); it++) {
if ((*it)->left!=NULL)
tmp.push_back((*it)->left);
if ((*it)->right!=NULL)
tmp.push_back((*it)->right);
}
}
vector> result;
while(!result_stack.empty()) {
vector cur = result_stack.top();
vector:: iterator it;
vector same_height_node;
for(it = cur.begin(); it < cur.end(); it++)
same_height_node.push_back((*it)->val);
result.push_back(same_height_node);
result_stack.pop();
}
return result;
} |
f*********m
发帖数: 726 | |
C***U
发帖数: 2406 | 14 为什么不是?
【在 I*********e 的大作中提到】
: 可以從上往下一行一行的讀，存到一個臨時的vector >,輸出的時候可以
: 到這輸出這個vector >。不過這恐怕不是題目要求的做法吧？
|
d******i
发帖数: 76 | 15 @lyclyc 的解法很赞， 学习到了，感谢, 有个小bug, root == NULL的情况
看到这个解法，感觉自己的码也太烂了。
我用递归写的，首先得到树的height，然后在对每个height进行递归。 |
i**********e
发帖数: 1145 | 16 我贡献一个 Depth-first 递归的解法。
这里注意 ret 是vector, insert() 复杂度是linear to ret.size().
可以改用 double-ended queue 来优化，最后转换回 vector 就好了.
vector > levelOrderBottom(TreeNode *root) {
vector > ret;
traverse(root, 0, ret);
return ret;
}
void traverse(TreeNode *p, int level, vector > &ret) {
if (!p) return;
if (ret.size() <= level) ret.insert(ret.begin(), vector());
traverse(p->left, level+1, ret);
traverse(p->right, level+1, ret);
ret[ret.size() - level - 1].push_back(p->val);
} |
e******o
发帖数: 757 | 17 如果是分层从底部打印到屏幕上而不是打印到vector > 里面有什么更好
的办法么？ |
