V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐关注
Meteor
JSLint - a JavaScript code quality tool
jsFiddle
D3.js
WebStorm
推荐书目
JavaScript 权威指南第 5 版
Closure: The Definitive Guide
mopig
V2EX  ›  JavaScript

Leetcode 的一个后序遍历二叉树: 求帮忙看看以下代码有什么问题?

  •  
  •   mopig · 2015-04-16 01:49:46 +08:00 · 2514 次点击
    这是一个创建于 3270 天前的主题,其中的信息可能已经有所发展或是发生改变。

    大半夜, 递归的有点乱...

    原题:Binary Tree Postorder Traversal


    /**
     * Definition for binary tree
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    
    /**
     * @param {TreeNode} root
     * @returns {number[]}
     */
    var postorderTraversal = function(root) {
      if(!result) var result = [];
      if (!root) return result;
    
      if (root.left) postorderTraversal(root.left);
      if (root.right) postorderTraversal(root.right);
      result.push(root.val);
    
      return result;
    };
    
    14 条回复    2015-04-17 11:58:01 +08:00
    monkeylyf
        1
    monkeylyf  
       2015-04-16 02:19:33 +08:00   ❤️ 1
    你的container result 是怎么个逻辑 return了但是不赋值? 第一感觉问题是出在这 不管input是什么你永远return []吧
    keyanzhang
        2
    keyanzhang  
       2015-04-16 02:51:31 +08:00   ❤️ 1
    mopig
        3
    mopig  
    OP
       2015-04-16 11:21:09 +08:00
    @monkeylyf 我也感觉是 return 出问题了, 就是想不明白, 出啥问题了...

    @keyanzhang 这代码逻辑清晰. 能帮忙解释下 我的代码 的硬伤在哪吗?
    slayer
        4
    slayer  
       2015-04-16 11:53:24 +08:00
    @mopig 第一行 result 还没有定义的话可以这样判断?表示不太懂js。
    mopig
        5
    mopig  
    OP
       2015-04-16 12:00:17 +08:00
    @slayer 第一行的单句执行是没有问题的.
    slayer
        6
    slayer  
       2015-04-16 12:11:07 +08:00   ❤️ 1
    @mopig 你每次递归都会新建一个result,之前result没有进入递归,所以需要一个单独的递归函数,像@keyanzhang 那样对同一个result操作。
    mopig
        7
    mopig  
    OP
       2015-04-16 14:02:32 +08:00
    @slayer 里面的递归调用 不能读取到外边的 result 吗?
    cheng007
        8
    cheng007  
       2015-04-16 19:29:08 +08:00   ❤️ 1
    function postorderTraversal (root, result) {
    if (!root) {
    return;
    }
    if (root.left) postorderTraversal(root.left, result) ;
    if (root.right) postorderTraversal(root.left, result);
    result.push(root.val)
    }
    var result = {};
    postorderTraversal(root, result);
    这样写呢?
    cheng007
        9
    cheng007  
       2015-04-16 19:31:53 +08:00
    递归尽量写程尾递归的形式,不然不断的压栈会内存会被大量占用,被搞死的。
    mopig
        10
    mopig  
    OP
       2015-04-16 22:58:05 +08:00
    @cheng007 result 定义在外边是能行的.
    slayer
        11
    slayer  
       2015-04-17 06:09:55 +08:00   ❤️ 1
    @mopig 你那result其实在递归函数里面的
    monkeylyf
        12
    monkeylyf  
       2015-04-17 06:15:18 +08:00   ❤️ 1
    @mopig 一般来说这种在递归的时候收集信息的写法 有2种常见的控制container(你的result)的做法
    第一种是设置一个global 的container 就像@keyanzhang 的做法一样 这样你在递归的时候就只负责把设计到的数据加进这个global container就行了
    第二种是在每一层都return一个在这个层收集到的信息 然后由上一层来做merge

    我感觉你贴出来的代码是倾向于第二种做法 但是你在调用递归的时候并没有对返回值进行任何操作
    画个tree的图出来会帮助你理解递归具体是什么个顺序
    hyesun
        13
    hyesun  
       2015-04-17 11:56:58 +08:00   ❤️ 1
    如果js的作用域跟我理解的差不多的话,你的result作用域只属于函数;所以当你递归处理root.left时,那个递归函数里的result还是空的。我猜测(因为现在忙里偷闲没时间测试),你需要在if语句里把递归函数返回的result的元素push进当前函数的result里
    hyesun
        14
    hyesun  
       2015-04-17 11:58:01 +08:00
    如果你把result定义在外面,那么每次递归函数插入的元素都在同一个result里,就没问题。估计是个作用域的问题
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   953 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 21:35 · PVG 05:35 · LAX 14:35 · JFK 17:35
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.