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

[run2016]

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

       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 却无法再次被遍历到无法入数组了，这个该如何解决呢？
• 这个可以用队列循环的思路来做，但是如果用递归如何完成呢？ 谢谢各位大大。

在下最近被递归，特别是 递归中返回值利用 ，还有 临时的压栈值 给搞糊涂了，如果有相关的教程或者书籍推荐，在下真是不甚感激啊！！

此问题已解决，谢谢各位大大！

今后有同学看到该帖时，如与我有相同疑惑，可参见 9楼 srip 同学提供的 思路。 祝大家刷题愉快~

[Kilerd]

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

[raysonx]

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

[run2016]

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

[AlisaDestiny]

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

[Heinz]

用栈更简单吧

[run2016]

@Heinz 怎么说？

[markx]

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

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

[mind3x]

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

[srlp]

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

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

[czheo]

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

[markx]

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

[neosfung]

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

[zhy0216]

BFS 啊 朋友...

[mind3x]

@markx
@neosfung

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

[mind3x]

@neosfung
@markx

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

[neosfung]

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

[mind3x]

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

[markx]

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

[czheo]

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

[mind3x]

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

[markx]

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

[markx]

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

[mind3x]

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

[wsy2220]

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

[mind3x]

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

[markx]

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