剑指 Offer 27. 二叉树的镜像

题目描述

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

例如输入：

     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

注意：本题与主站 226 题相同：https://leetcode-cn.com/problems/invert-binary-tree/

解题思路

这个题要考虑后序遍历。
假设已经遍历到最小单元，那么只需要将左子树和右子树互换，并返回root即可，即

root.left, root.right = root.right, root.left
return root

由于后序遍历的特性，最后一次遍历正好返回真正的root，两边是两棵已经镜像过了的大子树。
由于后序遍历最后返回的是root，所以最终返回的root就是已经镜像好的根节点。

解题代码

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

执行结果

执行用时：44 ms, 在所有 Python3 提交中击败了17.36%的用户
内存消耗：14.9 MB, 在所有 Python3 提交中击败了60.62%的用户