请教递归，有兴趣同学进啊

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2880 天前的主题，其中的信息可能已经有所发展或是发生改变。

先谢谢各位大大~
如下一棵树：

       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 同学提供的思路。祝大家刷题愉快~

数组

节点

vector

layer

27 条回复 • 2017-01-15 00:27:09 +08:00

Kilerd

2017-01-12 12:08:58 +08:00 via iPhone

按层遍历而已。挺简单的啊。请预习数据结构。😃😃😃

raysonx

2017-01-12 12:14:14 +08:00 via Android

从上往下，从右往左进行广度优先遍历，再逆序

run2016

2017-01-12 12:28:56 +08:00

@Kilerd
@raysonx
谢谢大大，这种遍历一般都是用队列循环思路。请问这类问题用递归可解吗？最近在练习这个。。

AlisaDestiny

2017-01-12 12:33:58 +08:00

循环+stack = 深度优先遍历（深搜）
循环+queue = 广度优先遍历（广搜）

Heinz

2017-01-12 13:21:58 +08:00 via iPhone

用栈更简单吧

run2016

2017-01-12 13:38:33 +08:00

@Heinz 怎么说？

markx

2017-01-12 13:45:15 +08:00

第一反应是用层序遍历，然后把每一层的合起来就好了。层序遍历嘛，就感觉用循环比较容易。如果想要语法形式上的递归的话，用一个新的函数，把循环的时候的变量作为参数传进函数就好了。好像这样就是尾递归而已，如果用不支持循环的语言来实现的话，可能就只能这样了。

如果形式上的递归还不够，一定要用递归的方法的话，我也没想到要怎么做……

mind3x

2017-01-12 16:52:17 +08:00 via Android

树的先序 /中序 /后序遍历，说层序什么的请重修数据结构，谢谢。

srlp

2017-01-12 17:11:27 +08:00 via iPhone

关键词 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)

lrigi

2017-01-12 17:54:27 +08:00 via iPhone

递归的话，先序 /中序 /后序遍历整颗树
然后对每个节点的深度进行标号入队
然后按深度 1234 逐个出队就好了吧

czheo

2017-01-12 21:01:27 +08:00

bfs 用递归不是蛋疼嘛？乖乖循环多好。
https://gist.github.com/czheo/92fafe0dd18e05d41d71e36bfd0b04e1

markx

2017-01-12 22:14:12 +08:00

@mind3x 那要请教 Level Order Tree Traversal 是该用先序、中序还是后序呢？

neosfung

2017-01-12 22:58:20 +08:00

@mind3x 挺好奇按照你说的这三种方法怎样输出楼主的结果

zhy0216

2017-01-13 08:00:17 +08:00

BFS 啊朋友...

mind3x

2017-01-13 17:48:04 +08:00

@markx
@neosfung

这个问题里面只要确保同一个节点的子节点访问顺序是先左后右，用先 /中 /后序遍历都可以，只是在 DFS 递归时要额外携带当前深度信息，以及按深度区分的二维结果数组，遍历完成后组合结果即可。

mind3x

2017-01-13 18:01:40 +08:00

@neosfung
@markx

用 BFS 非递归实现也可以。如果不考虑移出队列的操作， BFS 时所使用的队列中最后的内容其实已经接近这题目所要求的结果，只是在按层数排列上是相反的。
实做的时候，在 BFS 中增加一个额外的二维数组，每次有节点放进 BFS 队列时同时更新这个二维数组即可。
实现效率上因为是迭代式的，会比递归算法高效很多。

neosfung

2017-01-13 18:30:39 +08:00

@mind3x czheo 同学给出的方法就是先右后左哦。我挺奇怪的是，回复问题只说访问子节点的顺序，算是解决问题了么？

mind3x

2017-01-13 19:13:22 +08:00

@neosfung 大概你没仔细看，我说的是在 DFS 递归实现时需要先左后右。 @czheo 给出的是在 BFS 时通过先右后左的办法，最后再一次 reverse ，既解决了我上面说的正常 BFS 时层数顺序相反的问题，也无需用到二维数组。
至于我最开始的回复，只是吐槽层序这个说法而已。

markx

2017-01-14 02:47:26 +08:00

@mind3x 层序这个说法有什么可以吐槽的呢？

czheo

2017-01-14 07:41:25 +08:00

你们到底在瞎逼逼啥，我不是都给出答案了吗， bfs 十行代码的问题。 talk is cheap 。。。

mind3x

2017-01-14 11:21:16 +08:00 via Android

@markx 因为我觉得层序是描述的这个问题本身而不是解法。

markx

2017-01-14 13:13:55 +08:00

@mind3x 那你仍然觉得我应该重修数据结构吗？

markx

2017-01-14 13:18:50 +08:00

@czheo 瞎逼逼当然就是没目的地逼逼。 lol

mind3x

2017-01-14 17:15:43 +08:00 via Android

@markx 既然你问到了，从你上面的回答来看，我觉得是的，你应该重修数据结构 :D 为了避免彼此在这么无聊的问题上继续浪费时间，不如让我们愉快的互相拉黑吧 :))

wsy2220

2017-01-14 17:49:49 +08:00

层序遍历一遍再反过来就好了

mind3x

2017-01-14 17:53:56 +08:00 via Android

@markx 抱歉，又想了想，确实是我在抬杠，请接受我的歉意。总觉得自己已经过了上网和人瞎逼逼的年龄，看来还是自己修炼不够。

markx

2017-01-15 00:27:09 +08:00

@mind3x 好的，那就🤝。我一般也不在网上跟人争，但是之前莫名其妙被叫要去重修，关键是不说明原因，我实在是很不爽。大家都是读书人，还是应该就事论事，创造一个良好的氛围。如果你去 stackoverflow 和 quora ，即便别人说的再傻，我估计你也不会这样说。我个人觉得国内的社区氛围没那么好，每个人都有责任。