var invertTree = function(root) {
if(root === null) return null;
var temp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(temp);
return root;
};
var invertTree = function(root) {
if(root === null) return;
// swap left and right child
var temp = root.left;
root.left = root.right;
root.right = temp;
// recurse into children
invertTree(root.left);
invertTree(root.right);
};
这两个程序的递归细节是一样的吗？
回复 (16)
第一个函数最后由return语句返回传给函数的节点 root.left = invertTree(root.right); 可以翻成 ==> root.left =root.right； invertTree(root.right)；
二者的区别在于交换子树木的节点和赋值的先后关系 （answer from kikong）
第二种看起来清晰一点。细节的话无所谓，结果一样就好了。
用 mutable data 写递归, 只是顺序不一样, 没啥本质差别.
@QuoniamYIF @alsotang @jiyinyiyong 这里应该是二叉树的节点交换吧，我想问下这里的递归涉及到尾递归优化么？很明显两种写法还是有差别
考虑到 JavaScript 本身没有进行尾递归优化... 我认为这方面没有差别.
而且 return 看起来怪怪的..
@jiyinyiyong ES6 babel转码的时候进行了尾递归优化 @QuoniamYIF 能不能提供下数据结构
看上去没有符合尾递归的条件, 首先递归调用就不是在 return 后边的.
@jiyinyiyong 它这里两次递归调用，所以我也不知道怎么尾递归优化。希望知道数据结构，最好搞个特别大的数据模拟下。但是看代码感觉数据结构有点问题，搞不懂
如果那样的话, 我建议拆分成 3 个函数, 一个是处理 root, 一个处理 left, 一个处理 right. 这样 3 个依次循环, 每个都是尾递归, 按说能达到效果. 递归的状态和递归的位置那样的话都要放在函数参数传递了.
@jiyinyiyong
{
left: {
left: {
left: {},
right: {}
},
right: {
left: {},
right: {}
}
},
right: {
left: {
left: {},
right: {}
},
right: {
left: {},
right: {}
}
}
}
根据方法，我感觉数据结构是这样的，不过有啥意义？
tree 的结构用 JSON 去模拟大概也就这样吧, 等作者回复啰
@yuyang041060120 原题里有数据结构实现的方式 vert-binary-tree
@yuyang041060120 已经可以尾递归优化了？
@firefox 两次调用，一时我还真不知道怎么优化，在想想想
@jiyinyiyong 两次调用，我没有想到怎么优化，大哥有啥idea没
既然是 mutable 数据直接用 while 去维护就好了... 这里尾递归似乎没有意思.