226. 翻转二叉树

Difficulty
easy
Tags
二叉树
URL
https://leetcode-cn.com/problems/invert-binary-tree/
Star
翻转一棵二叉树。
示例：
输入：
     4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：
     4
   /   \
  7     2
 / \   / \
9   6 3   1
备注: 这个问题是受到 Max Howell 的 原问题 启发的 ：
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。

法1 宽度优先搜索

思路
层次遍历，将逐个节点的左右节点互换
题解
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return root
        queue = []
        queue.append(root)
        while len(queue) > 0:
            temp_node = queue.pop(0)
            temp_node.left, temp_node.right = temp_node.right, temp_node.left
            
            if temp_node.left :
                queue.append(temp_node.left)
            if temp_node.right:
                queue.append(temp_node.right)
                
        return root

法2：深度优先搜索

递归法

思路
递归法， 前序后序遍历均可以，就是将每一个节点的左右子节点互换即可
中序遍历也可以，但是如果直接用中序遍历，则会将部分节点（非叶子节点）翻转两次，这样就等于没反转了
题解
前序遍历
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return
        else:
            root.left, root.right = root.right, root.left
            self.invertTree(root.left)
            self.invertTree(root.right)
            return root
后序遍历
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return
        else:
            self.invertTree(root.left)
            self.invertTree(root.right)
						root.left, root.right = root.right, root.left
            return root
中序遍历
注：代码看似反转了两次左子树，但其实只反转了一次，因为第二次反转左子树的时候，其实是反转的原先的右子树
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return
        else:
            self.invertTree(root.left)
            root.left, root.right = root.right, root.left
            self.invertTree(root.left)
            return root

迭代法

思路
采用迭代方法遍历二叉树，将遍历的每个节点的左右子树反转即可.
前序、中序均可
题解
前序遍历
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return root
        stack = []
        stack.append(root)
        while len(stack) > 0:
            node = stack.pop()
            node.left, node.right = node.right, node.left
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return root
中序遍历
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return root
        stack = []
        cur = root
        while len(stack) > 0 or cur:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                cur.left, cur.right = cur.right, cur.left
                # 此处与二叉树中序遍历不同， 必须为 cur.left 因为上一步将其反转了
								cur = cur.left 
        return root