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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

推荐关注

› Meteor

› JSLint - a JavaScript code quality tool

› jsFiddle

› D3.js

› WebStorm

推荐书目

› JavaScript 权威指南第 5 版

› Closure: The Definitive Guide

这是一个创建于 3500 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

原题: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;
};

treenode

root.right

root.left

14 条回复 • 2015-04-17 11:58:01 +08:00

monkeylyf

2015-04-16 02:19:33 +08:00

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

keyanzhang

2015-04-16 02:51:31 +08:00

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

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

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里，就没问题。估计是个作用域的问题