关于递归的理解？

Question

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

这两个程序的递归细节是一样的吗？

Answer 1

交换树的左右节点
从一个节点出发,那就是left和right相互交换

var temp = root.left;
root.left = root.right
root.right = temp;
return root;

如果代码这样写，只是简单地做到了一个节点下的left、right交换，left、right下的节点并没有进行左右交换，要知道left、right下也可能是有节点的，那么需要进入left/right节点，交换其下的左右节点，这个过程和上面的过程相同，这个过程可以一直进行下去，直到其节点下面没有子节点，不需要再交换，这个条件就是if(root === null) return null;

Answer 2

不明白难点在哪里…… 这不就是大名鼎鼎的反转二叉树么……

如果你明白什么是反转二叉数的话，那应该很容易理解，我们要做的就是把每个节点的 left child 和 right child 互换。在 JavaScript 里 swap 两个变量需要手动写临时变量 temp。而要遍历每个节点做这样的处理，递归到它的 children 是必要的。

事实上在这个 case 里，invertTree 函数没有必要有返回值，因为它返回的就是它的参数 root。所以加上返回值可能反而有点 confusion。也许像下面这么写反而更容易看懂：

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

Answer 3

这不是google的面试题吗233

题目是反转二叉树对吧，那么从根节点出发，反转左孩子，反转右孩子，交换左右孩子，over

注:以上三个操作可乱序进行