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

[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;
};

[monkeylyf]

你的container result 是怎么个逻辑 return了但是不赋值? 第一感觉问题是出在这 不管input是什么你永远return []吧

[keyanzhang]

https://gist.github.com/anonymous/9ab30fe668e1244d38af

[mopig]

@monkeylyf 我也感觉是 return 出问题了, 就是想不明白, 出啥问题了...

@keyanzhang 这代码逻辑清晰. 能帮忙解释下 我的代码 的硬伤在哪吗?

[slayer]

@mopig 第一行 result 还没有定义的话可以这样判断？表示不太懂js。

[mopig]

@slayer 第一行的单句执行是没有问题的.

[slayer]

@mopig 你每次递归都会新建一个result，之前result没有进入递归，所以需要一个单独的递归函数，像@keyanzhang 那样对同一个result操作。

[mopig]

@slayer 里面的递归调用 不能读取到外边的 result 吗?

[cheng007]

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]

递归尽量写程尾递归的形式，不然不断的压栈会内存会被大量占用，被搞死的。

[mopig]

@cheng007 result 定义在外边是能行的.

[slayer]

@mopig 你那result其实在递归函数里面的

[monkeylyf]

@mopig 一般来说这种在递归的时候收集信息的写法 有2种常见的控制container(你的result)的做法
第一种是设置一个global 的container 就像@keyanzhang 的做法一样 这样你在递归的时候就只负责把设计到的数据加进这个global container就行了
第二种是在每一层都return一个在这个层收集到的信息 然后由上一层来做merge

我感觉你贴出来的代码是倾向于第二种做法 但是你在调用递归的时候并没有对返回值进行任何操作
画个tree的图出来会帮助你理解递归具体是什么个顺序

[hyesun]

如果js的作用域跟我理解的差不多的话，你的result作用域只属于函数；所以当你递归处理root.left时，那个递归函数里的result还是空的。我猜测（因为现在忙里偷闲没时间测试），你需要在if语句里把递归函数返回的result的元素push进当前函数的result里

[hyesun]

如果你把result定义在外面，那么每次递归函数插入的元素都在同一个result里，就没问题。估计是个作用域的问题