› Closure: The Definitive Guide
大半夜, 递归的有点乱...
原题: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;
};
 |
1
monkeylyf Apr 16, 2015  1
你的container result 是怎么个逻辑 return了但是不赋值? 第一感觉问题是出在这 不管input是什么你永远return []吧
|
 |
2
keyanzhang Apr 16, 2015 1
|
 |
3
mopig OP |
 |
6
slayer Apr 16, 2015 1
@mopig 你每次递归都会新建一个result，之前result没有进入递归，所以需要一个单独的递归函数，像@keyanzhang 那样对同一个result操作。
|
 |
8
cheng007 Apr 16, 2015 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); 这样写呢？ |
|
9
cheng007 Apr 16, 2015
递归尽量写程尾递归的形式，不然不断的压栈会内存会被大量占用，被搞死的。
|
|
12
monkeylyf Apr 17, 2015 1
@mopig 一般来说这种在递归的时候收集信息的写法 有2种常见的控制container(你的result)的做法
第一种是设置一个global 的container 就像@keyanzhang 的做法一样 这样你在递归的时候就只负责把设计到的数据加进这个global container就行了 第二种是在每一层都return一个在这个层收集到的信息 然后由上一层来做merge 我感觉你贴出来的代码是倾向于第二种做法 但是你在调用递归的时候并没有对返回值进行任何操作 画个tree的图出来会帮助你理解递归具体是什么个顺序 |
 |
13
hyesun Apr 17, 2015 1
如果js的作用域跟我理解的差不多的话，你的result作用域只属于函数；所以当你递归处理root.left时，那个递归函数里的result还是空的。我猜测（因为现在忙里偷闲没时间测试），你需要在if语句里把递归函数返回的result的元素push进当前函数的result里
|
|
14
hyesun Apr 17, 2015
如果你把result定义在外面，那么每次递归函数插入的元素都在同一个result里，就没问题。估计是个作用域的问题
|
Select Language