LeetCode226：翻转二叉树

目录

一、题目

二、示例

三、思路

四、代码

一、题目

翻转一棵二叉树。

二、示例

输入：

       4

     /   \

   2     7

  /  \   /  \

1   3 6   9

输出：

       4

     /   \

   7     2

  /  \   /  \

9   6 3   1

备注:

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

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

三、思路

1、先序遍历交换左右子树

2、中序遍历交换左右子树

3、后序遍历交换左右子树

四、代码

1、方法1

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        """
        :type root: TreeNode
        :rtype: TreeNode
        """

        # 先序
        def Inverse1(root):
            if root is None:
                return
            tmp = root.left
            root.left = root.right
            root.right = tmp
            Inverse1(root.left)
            Inverse1(root.right)
        Inverse1(root)
        return root

if __name__ == '__main__':
    root = TreeNode(4)
    root.left = TreeNode(2)
    root.right = TreeNode(7)
    root.left.left = TreeNode(1)
    root.left.right = TreeNode(3)
    root.right.left = TreeNode(6)
    root.right.right = TreeNode(9)
    s = Solution()
    new_Tree = s.invertTree(root)
    print(new_Tree.val, new_Tree.left.val, new_Tree.right.val)
           

2、方法2

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        """
        :type root: TreeNode
        :rtype: TreeNode
        """

        # 中序
        def Inverse2(root):
            if root is None:
                return
            Inverse2(root.left)
            tmp = root.left
            root.left = root.right
            root.right = tmp
            Inverse2(root.left)
        Inverse2(root)
        return root

if __name__ == '__main__':
    root = TreeNode(4)
    root.left = TreeNode(2)
    root.right = TreeNode(7)
    root.left.left = TreeNode(1)
    root.left.right = TreeNode(3)
    root.right.left = TreeNode(6)
    root.right.right = TreeNode(9)
    s = Solution()
    new_Tree = s.invertTree(root)
    print(new_Tree.val, new_Tree.left.val, new_Tree.right.val)
           

3、方法3

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        """
        :type root: TreeNode
        :rtype: TreeNode
        """

        # 后序
        def Inverse(root):
            if not root:
                return
            Inverse(root.left)
            Inverse(root.right)
            tmp = root.right
            root.right = root.left
            root.left = tmp
        Inverse(root)
        return root

if __name__ == '__main__':
    root = TreeNode(4)
    root.left = TreeNode(2)
    root.right = TreeNode(7)
    root.left.left = TreeNode(1)
    root.left.right = TreeNode(3)
    root.right.left = TreeNode(6)
    root.right.right = TreeNode(9)
    s = Solution()
    new_Tree = s.invertTree(root)
    print(new_Tree.val, new_Tree.left.val, new_Tree.right.val)