先谢谢各位大大~
如下一棵树:
1
/ \
2 9
/ \ / \
3 4 5 6
/ \
9 10
传入一棵树头节点,导出的结果应该是从下往上 从左往右顺序的数组
上述的导出应该是[9,10,3,4,5,6,2,9,1]
这样的数组
vector<int> tree_leaf(TreeNode* note) {
}
我考虑了个思路,但是没能写出运行成功的代码,希望前辈指教啊。。
int layer
记录当前的层级 ,在全局用一个vector<vector<int>>array
的方形矩阵记录下每个层级的值array[layer].pushback(current_note.value)
在下最近被递归,特别是 递归中返回值利用 ,还有 临时的压栈值 给搞糊涂了,如果有相关的教程或者书籍推荐,在下真是不甚感激啊!!
此问题已解决,谢谢各位大大!
今后有同学看到该帖时,如与我有相同疑惑,可参见 9楼 srip 同学提供的 思路。 祝大家刷题愉快~
1
Kilerd 2017-01-12 12:08:58 +08:00 via iPhone
按层遍历而已。挺简单的啊。请预习数据结构。😃😃😃
|
2
raysonx 2017-01-12 12:14:14 +08:00 via Android
从上往下,从右往左进行广度优先遍历,再逆序
|
3
run2016 OP |
4
AlisaDestiny 2017-01-12 12:33:58 +08:00
循环+stack = 深度优先遍历(深搜)
循环+queue = 广度优先遍历(广搜) |
5
Heinz 2017-01-12 13:21:58 +08:00 via iPhone
用栈更简单吧
|
7
markx 2017-01-12 13:45:15 +08:00
第一反应是用层序遍历, 然后把每一层的合起来就好了。 层序遍历嘛,就感觉用循环比较容易。 如果想要语法形式上的递归的话, 用一个新的函数,把循环的时候的变量作为参数传进函数就好了。好像这样就是尾递归而已,如果用不支持循环的语言来实现的话,可能就只能这样了。
如果形式上的递归还不够,一定要用递归的方法的话,我也没想到要怎么做…… |
8
mind3x 2017-01-12 16:52:17 +08:00 via Android
树的先序 /中序 /后序遍历,说层序什么的请重修数据结构,谢谢。
|
9
srlp 2017-01-12 17:11:27 +08:00 via iPhone 1
关键词 level order traversal dfs 。
代码可参考 https://siddontang.gitbooks.io/leetcode-solution/content/tree/binary_tree_level_order_traversal.html 最后把 vector of vector 压扁即可。 具体说到你的思路,在这题目中不需要返回值,因为你不需要把东西返回给上一层,一直向下遍历把数字塞到 vector of vector 内部就可以了(因为你最后才把 vector of vector 拍扁)。你需要实现的是这么一个递归函数 void dfs(vector<vector<int>> &array, TreeNode *node, int curr_level) |
10
lrigi 2017-01-12 17:54:27 +08:00 via iPhone
递归的话,先序 /中序 /后序 遍历整颗树
然后对每个节点的深度进行标号 入队 然后按深度 1234 逐个出队就好了吧 |
11
czheo 2017-01-12 21:01:27 +08:00 2
bfs 用递归不是蛋疼嘛? 乖乖循环多好。
https://gist.github.com/czheo/92fafe0dd18e05d41d71e36bfd0b04e1 |
14
zhy0216 2017-01-13 08:00:17 +08:00
BFS 啊 朋友...
|
15
mind3x 2017-01-13 17:48:04 +08:00
|
16
mind3x 2017-01-13 18:01:40 +08:00
|
18
mind3x 2017-01-13 19:13:22 +08:00
|
20
czheo 2017-01-14 07:41:25 +08:00
你们到底在瞎逼逼啥,我不是都给出答案了吗, bfs 十行代码的问题。 talk is cheap 。。。
|
24
mind3x 2017-01-14 17:15:43 +08:00 via Android
@markx 既然你问到了,从你上面的回答来看,我觉得是的,你应该重修数据结构 :D 为了避免彼此在这么无聊的问题上继续浪费时间,不如让我们愉快的互相拉黑吧 :))
|
25
wsy2220 2017-01-14 17:49:49 +08:00
层序遍历一遍再反过来就好了
|