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

2015-04-16 01:49:46 +08:00
 mopig

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

原题: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;
};
2639 次点击
所在节点    JavaScript
14 条回复
monkeylyf
2015-04-16 02:19:33 +08:00
你的container result 是怎么个逻辑 return了但是不赋值? 第一感觉问题是出在这 不管input是什么你永远return []吧
keyanzhang
2015-04-16 02:51:31 +08:00
mopig
2015-04-16 11:21:09 +08:00
@monkeylyf 我也感觉是 return 出问题了, 就是想不明白, 出啥问题了...

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

我感觉你贴出来的代码是倾向于第二种做法 但是你在调用递归的时候并没有对返回值进行任何操作
画个tree的图出来会帮助你理解递归具体是什么个顺序
hyesun
2015-04-17 11:56:58 +08:00
如果js的作用域跟我理解的差不多的话,你的result作用域只属于函数;所以当你递归处理root.left时,那个递归函数里的result还是空的。我猜测(因为现在忙里偷闲没时间测试),你需要在if语句里把递归函数返回的result的元素push进当前函数的result里
hyesun
2015-04-17 11:58:01 +08:00
如果你把result定义在外面,那么每次递归函数插入的元素都在同一个result里,就没问题。估计是个作用域的问题

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/184021

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX