226. Invert Binary Tree

[qianlei90]

226. Invert Binary Tree

Tags: 印象笔记

[toc]

---

Question

Invert a binary tree.

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

to

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

Solution

又是二叉树又是二叉树，还是用递归啊。正确的思路是交换左右孩子节点，再利用递归重复操作。 第一次WA，思路错误，贴出思路错误的代码。

Show me the code(wrong)

这个想法是交换两个子节点的值，然后对子节点进行同样的操作。下面的是转换后的结果，这个结果是错误的。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root and root.left and root.right:
            left, right = root.left, root.right
            root.left = self.invertTree(right)
            root.right = self.invertTree(left)
        return root

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

to

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

Show me the code(right) 1

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root:
            root.left, root.right = root.right, root.left
            self.invertTree(root.left)
            self.invertTree(root.right)
        return root

Show me the code(right) 2

对上面的代码进行精简，精简到3行

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root:
            root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

- 完 -