68 - 翻转二叉树

题目

翻转一棵二叉树。

示例：

输入：

 4

/ 2 7 / / 1 3 6 9 输出：

 4

/ 7 2 / / 9 6 3 1 备注: 这个问题是受到 Max Howell 的 原问题 启发的 ：

谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。

解答

是不是我做出这道题，也能写出homebrew，进谷歌了？😂😂

递归

假设用这个方法，root下面每个节点都转好了，那么该怎么转现在的两个节点呢？

var invertTree = function (root) {
  if (root === null) {
    return null;
  }
  let temp = invertTree(root.right)
  root.right = invertTree(root.left)
  root.left = temp
  return root
};

Runtime: 56 ms, faster than 51.74% of JavaScript online submissions for Invert Binary Tree.

Memory Usage: 33.8 MB, less than 60.00% of JavaScript online submissions for Invert Binary Tree.

官方题解要多存一个变量，我觉的这样就行了

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    root.Right, root.Left = invertTree(root.Left), invertTree(root.Right)
    return root
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Invert Binary Tree.

Memory Usage: 2.2 MB, less than 66.67% of Go online submissions forInvert Binary Tree.

感觉go的一个好处是可以这样方便的互换，不用再麻烦的另外换变量。似乎python也可以？

看到了这个大佬的解法，原来js里面也能解构赋值。。

作者：jikunguo

链接：https://leetcode-cn.com/problems/invert-binary-tree/solution/js-di-gui-jie-gou-fu-zhi-by-jikunguo/

var invertTree = function (root) {
  if (root !== null) {
    [root.left, root.right] = [invertTree(root.right), invertTree(root.left)]
  }
  return root
};

Runtime: 56 ms, faster than 51.74% of JavaScript online submissions for Invert Binary Tree.

Memory Usage: 34 MB, less than 20.00% of JavaScript online submissions for Invert Binary Tree.

虽然好像占了很多内存，估计是因为强行新建了一个数组？

那么go也能这么写咯？

func invertTree(root *TreeNode) *TreeNode {
    if root != nil {
        root.Right, root.Left = invertTree(root.Left), invertTree(root.Right)
    }
    return root
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Invert Binary Tree.

Memory Usage: 2.2 MB, less than 66.67% of Go online submissions forInvert Binary Tree.

感觉go的优化要比js好？😂