这是一个创建于 2874 天前的主题，其中的信息可能已经有所发展或是发生改变。
先谢谢各位大大~
如下一棵树：
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的方形矩阵记录下每个层级的值 - 在这个逻辑中，递归退出的基点遍历到某节点左右树枝均为空，此时用返回层级为 0 ，并同时记录当前节点的值为
array[layer].pushback(current_note.value) - 根据上述逻辑。在图中 3 遍历完了的时候， 3 这个节点的 layer 还是没能拿到，此时回到 3 的父节点 2 ， 2 再去右子数遍历到 9 ，这时 array[0].pushback(9),但是之前的 3 却无法再次被遍历到无法入数组了，这个该如何解决呢？
- 这个可以用队列循环的思路来做，但是如果用递归如何完成呢？ 谢谢各位大大。
在下最近被递归，特别是 递归中返回值利用 ，还有 临时的压栈值 给搞糊涂了，如果有相关的教程或者书籍推荐，在下真是不甚感激啊！！
第 1 条附言 · 2017-01-13 11:16:42 +08:00
此问题已解决，谢谢各位大大！
今后有同学看到该帖时，如与我有相同疑惑，可参见 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
层序遍历一遍再反过来就好了
|
Select Language