Skip to main content

226. 翻转二叉树 [easy]

226. 翻转二叉树 [easy]​

https://leetcode-cn.com/problems/invert-binary-tree/

翻转一棵二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

备注:

  • 这个问题是受到 Max Howell 的 原问题 启发的 ：

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

    通过次数97,779提交次数128,857

连接上去看了一眼，这是2015年的推特

https://twitter.com/mxcl/status/608682016205344768?

image

First Try​

2020-07-21

本来觉得一个递归轻轻松松搞定，结果竟然出现莫名其妙的bug，差点没搞定。

用了个3节点树测试了一下，发现是直接用root.left=self.invertTree(root.right)之后，又执行了root.right = self.inverTree(root.left)，其实这时候的参数root.left已经不是之前的左节点。

修复后果然又恢复了正常的世界，bingo!

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return root 
        
        left = self.invertTree(root.right)
        right = self.invertTree(root.left)
        root.left = left 
        root.right = right 
        return root
  • 执行用时：36 ms, 在所有 Python3 提交中击败了88.14%的用户
  • 内存消耗：13.6 MB, 在所有 Python3 提交中击败了5.26%的用户
  • bug version

直接用root.left=self.invertTree(root.right)之后，又执行了root.right = self.inverTree(root.left)，其实这时候的参数root.left已经不是之前的左节点。 

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return root 
        
        root.left = self.invertTree(root.right)
        root.right = self.invertTree(root.left)
        return root