关于递归的理解？
发布于 5 个月前 作者 QuoniamYIF 462 次浏览 来自 问答 
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 去维护就好了… 这里尾递归似乎没有意思.

回到顶部