剑指Offer27-二叉树的镜

兴趣爱好交流 每日一题
1

剑指Offer27-二叉树的镜

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：


    4

  /   \

 2     7

/ \   / \

1   3 6   9

镜像输出：


    4

  /   \

 7     2

/ \   / \

9   6 3   1

示例 1：


输入：root = [4,2,7,1,3,6,9]

输出：[4,7,2,9,6,3,1]

限制：


0 <= 节点个数 <= 1000

来源：力扣（LeetCode）

链接：力扣

一解

递归遍历左右子树，进行交互：


# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

    def mirrorTree(self, root: TreeNode) -> TreeNode:

        if not root:

            return None

        # 进行交互

        tmp = root.right

        root.right = root.left

        root.left = tmp

        self.mirrorTree(root.left)

        self.mirrorTree(root.right)

        return root

二解

思路与上述相同。

self.mirrorTree(root.left)会获取“已交换左右子树”的左子树，可利用这点简化代码：


# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

    def mirrorTree(self, root: TreeNode) -> TreeNode:

        if not root: return

        root.right, root.left = self.mirrorTree(root.left), self.mirrorTree(root.right)

        return root
2 
class TreeNode:

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

    def __iter__(self):
        if self.left:
            yield self.left.val
        if self.right:
            yield self.right.val
        if self.left:
            yield from self.left
        if self.right:
            yield from self.right

    def to_list(self):
        return [self.val] + list(self)


root = TreeNode(4)

node1 = TreeNode(2)
node2 = TreeNode(7)
root.left = node1
root.right = node2

node3 = TreeNode(1)
node4 = TreeNode(3)
node1.left = node3
node1.right = node4

node5 = TreeNode(6)
node6 = TreeNode(9)
node2.left = node5
node2.right = node6


def mirror_tree(root_node: TreeNode):
    if not root_node:
        return
    root_node.left, root_node.right = mirror_tree(root_node.right), mirror_tree(root_node.left)
    return root_node


assert mirror_tree(root).to_list() == [4, 7, 2, 9, 6, 3, 1]