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好?😂

Last updated

Was this helpful?