226. Invert Binary Tree

Description

Invert a binary tree.

Example:

Input:

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

Output:

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

Trivia: This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

Solutions

　　将二叉树翻转得到镜像结果。

1. DFS-Recursion

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
# DFS-Recursion
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        left, right = root.left, root.right

        root.right = self.invertTree(left)
        root.left = self.invertTree(right)
        return root

# 68/68 cases passed (28 ms)
# Your runtime beats 67.8 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.6 MB)

　　或者：

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

        self.invertTree(root.left)
        self.invertTree(root.right)
        return root
# 68/68 cases passed (28 ms)
# Your runtime beats 67.73 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.8 MB)

　　更简洁版：

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

# 68/68 cases passed (24 ms)
# Your runtime beats 89.08 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.8 MB)

2. DFS-Iterative

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        stack = [root]
        while stack:
            node = stack.pop()
            node.right, node.left = node.left, node.right
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return root

# 68/68 cases passed (20 ms)
# Your runtime beats 97.49 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.6 MB)

3. BFS-Iterative

# BFS-Recursion
import collections
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        queue = collections.deque()
        queue.append(root)
        while queue:
            node = queue.popleft()
            node.right, node.left = node.left, node.right
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return root

# 68/68 cases passed (24 ms)
# Your runtime beats 89.08 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.7 MB)

References