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

有关镜像二叉树的疑问

  •  
  •   sneezry ·
    Sneezry · 2015-06-12 20:32:30 +08:00 · 2475 次点击
    这是一个创建于 3212 天前的主题,其中的信息可能已经有所发展或是发生改变。
    网上看到讨论镜像二叉树的问题多有不用递归的前提条件,如果用递归这个问题就简单多了。那么不用递归,基本也都用到了栈,那么问题是,用栈有什么实际上的好处吗?感觉用栈并不会节省空间,那么不用递归的要求仅仅是为了提高问题难度吗?在实际生产中,大家是如何处理镜像二叉树的?大家的考虑是怎样的?
    6 条回复    2015-06-13 10:59:56 +08:00
    sumhat
        1
    sumhat  
       2015-06-12 20:34:19 +08:00   ❤️ 2
    系统栈和用户栈的差别。递归的主要问题是会栈溢出,自己开的空间则不受这个限制。
    wy315700
        2
    wy315700  
       2015-06-12 20:34:24 +08:00   ❤️ 1
    日常编程中,一般会要求不使用递归,尤其是Python等语言,递归的性能简直低下。
    weyou
        3
    weyou  
       2015-06-12 21:00:16 +08:00   ❤️ 1
    除了@sumhat所讲的栈溢出的问题之外,使用用户栈会使性能提升,函数调用栈除了所操作的数据之外,还有函数参数的传递,返回值的拷贝等额外的开销。
    ffffwh
        4
    ffffwh  
       2015-06-12 22:53:41 +08:00   ❤️ 1
    万能法(前方装逼):递归->CPS->trampolining
    https://gist.github.com/unknownzerx/dffb4346fe2f7429423b

    性能?who cares...
    billlee
        5
    billlee  
       2015-06-12 23:02:31 +08:00   ❤️ 1
    递归的性能差,可能发生运行栈溢出。
    另外补充一点,遍历二叉树不一定用栈,深度优先遍历用栈,广度优先遍历用队列。
    hooluupog
        6
    hooluupog  
       2015-06-13 10:59:56 +08:00   ❤️ 1
    首先,不用递归并非完全是指用栈去模拟递归。栈模拟递归和非递归算法(比如迭代)是两个概念。

    很多情况下递归符合人的思维方式,但性能偏弱,而且有时候递归深度有限制,在没有尾递归优化的编译器上尤为如此。
    非递归的算法往往更难理解,但会获得较好的性能。
    比如汉诺塔问题,既可以用递归实现,又可以用栈去模拟递归,同时还有比较难以理解的非递归算法。
    同样Fibonacci问题也有非递归的解法,而实际环境中,命令式语言基本上都是去用非递归的方法去解Fibonacci类似的问题。很多人喜欢用Fibonacci递归算法去测试一个编程语言的性能,实际上这个是最坏的一种测试情形,和实际完全脱节。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5415 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 07:50 · PVG 15:50 · LAX 00:50 · JFK 03:50
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.