V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
run2016
V2EX  ›  程序员

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

  •  
  •   run2016 · 2017-01-12 12:04:41 +08:00 · 3396 次点击
    这是一个创建于 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 同学提供的 思路。 祝大家刷题愉快~

    27 条回复    2017-01-15 00:27:09 +08:00
    Kilerd
        1
    Kilerd  
       2017-01-12 12:08:58 +08:00 via iPhone
    按层遍历而已。挺简单的啊。请预习数据结构。😃😃😃
    raysonx
        2
    raysonx  
       2017-01-12 12:14:14 +08:00 via Android
    从上往下,从右往左进行广度优先遍历,再逆序
    run2016
        3
    run2016  
    OP
       2017-01-12 12:28:56 +08:00
    @Kilerd
    @raysonx
    谢谢大大,这种遍历一般都是用队列循环思路。 请问这类问题用递归可解吗? 最近在练习这个。。
    AlisaDestiny
        4
    AlisaDestiny  
       2017-01-12 12:33:58 +08:00
    循环+stack = 深度优先遍历(深搜)
    循环+queue = 广度优先遍历(广搜)
    Heinz
        5
    Heinz  
       2017-01-12 13:21:58 +08:00 via iPhone
    用栈更简单吧
    run2016
        6
    run2016  
    OP
       2017-01-12 13:38:33 +08:00
    @Heinz 怎么说?
    markx
        7
    markx  
       2017-01-12 13:45:15 +08:00
    第一反应是用层序遍历, 然后把每一层的合起来就好了。 层序遍历嘛,就感觉用循环比较容易。 如果想要语法形式上的递归的话, 用一个新的函数,把循环的时候的变量作为参数传进函数就好了。好像这样就是尾递归而已,如果用不支持循环的语言来实现的话,可能就只能这样了。

    如果形式上的递归还不够,一定要用递归的方法的话,我也没想到要怎么做……
    mind3x
        8
    mind3x  
       2017-01-12 16:52:17 +08:00 via Android
    树的先序 /中序 /后序遍历,说层序什么的请重修数据结构,谢谢。
    srlp
        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)
    lrigi
        10
    lrigi  
       2017-01-12 17:54:27 +08:00 via iPhone
    递归的话,先序 /中序 /后序 遍历整颗树
    然后对每个节点的深度进行标号 入队
    然后按深度 1234 逐个出队就好了吧
    czheo
        11
    czheo  
       2017-01-12 21:01:27 +08:00   ❤️ 2
    bfs 用递归不是蛋疼嘛? 乖乖循环多好。
    https://gist.github.com/czheo/92fafe0dd18e05d41d71e36bfd0b04e1
    markx
        12
    markx  
       2017-01-12 22:14:12 +08:00
    @mind3x 那要请教 Level Order Tree Traversal 是该用先序、中序还是后序呢?
    neosfung
        13
    neosfung  
       2017-01-12 22:58:20 +08:00
    @mind3x 挺好奇按照你说的这三种方法怎样输出楼主的结果
    zhy0216
        14
    zhy0216  
       2017-01-13 08:00:17 +08:00
    BFS 啊 朋友...
    mind3x
        15
    mind3x  
       2017-01-13 17:48:04 +08:00
    @markx
    @neosfung

    这个问题里面只要确保同一个节点的子节点访问顺序是先左后右,用先 /中 /后序遍历都可以,只是在 DFS 递归时要额外携带当前深度信息,以及按深度区分的二维结果数组,遍历完成后组合结果即可。
    mind3x
        16
    mind3x  
       2017-01-13 18:01:40 +08:00
    @neosfung
    @markx

    用 BFS 非递归实现也可以。如果不考虑移出队列的操作, BFS 时所使用的队列中最后的内容其实已经接近这题目所要求的结果,只是在按层数排列上是相反的。
    实做的时候,在 BFS 中增加一个额外的二维数组,每次有节点放进 BFS 队列时同时更新这个二维数组即可。
    实现效率上因为是迭代式的,会比递归算法高效很多。
    neosfung
        17
    neosfung  
       2017-01-13 18:30:39 +08:00
    @mind3x czheo 同学给出的方法就是先右后左哦。我挺奇怪的是,回复问题只说访问子节点的顺序,算是解决问题了么?
    mind3x
        18
    mind3x  
       2017-01-13 19:13:22 +08:00
    @neosfung 大概你没仔细看,我说的是在 DFS 递归实现时需要先左后右。 @czheo 给出的是在 BFS 时通过先右后左的办法,最后再一次 reverse ,既解决了我上面说的正常 BFS 时层数顺序相反的问题,也无需用到二维数组。
    至于我最开始的回复,只是吐槽层序这个说法而已。
    markx
        19
    markx  
       2017-01-14 02:47:26 +08:00
    @mind3x 层序这个说法有什么可以吐槽的呢?
    czheo
        20
    czheo  
       2017-01-14 07:41:25 +08:00
    你们到底在瞎逼逼啥,我不是都给出答案了吗, bfs 十行代码的问题。 talk is cheap 。。。
    mind3x
        21
    mind3x  
       2017-01-14 11:21:16 +08:00 via Android
    @markx 因为我觉得层序是描述的这个问题本身而不是解法。
    markx
        22
    markx  
       2017-01-14 13:13:55 +08:00
    @mind3x 那你仍然觉得我应该重修数据结构吗?
    markx
        23
    markx  
       2017-01-14 13:18:50 +08:00
    @czheo 瞎逼逼当然就是没目的地逼逼。 lol
    mind3x
        24
    mind3x  
       2017-01-14 17:15:43 +08:00 via Android
    @markx 既然你问到了,从你上面的回答来看,我觉得是的,你应该重修数据结构 :D 为了避免彼此在这么无聊的问题上继续浪费时间,不如让我们愉快的互相拉黑吧 :))
    wsy2220
        25
    wsy2220  
       2017-01-14 17:49:49 +08:00
    层序遍历一遍再反过来就好了
    mind3x
        26
    mind3x  
       2017-01-14 17:53:56 +08:00 via Android
    @markx 抱歉,又想了想,确实是我在抬杠,请接受我的歉意。总觉得自己已经过了上网和人瞎逼逼的年龄,看来还是自己修炼不够。
    markx
        27
    markx  
       2017-01-15 00:27:09 +08:00
    @mind3x 好的,那就🤝。 我一般也不在网上跟人争,但是之前莫名其妙被叫要去重修,关键是不说明原因,我实在是很不爽。 大家都是读书人,还是应该就事论事,创造一个良好的氛围。如果你去 stackoverflow 和 quora ,即便别人说的再傻,我估计你也不会这样说。 我个人觉得国内的社区氛围没那么好,每个人都有责任。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1156 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 18:53 · PVG 02:53 · LAX 10:53 · JFK 13:53
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.