【Leetcode】剑指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
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/er-cha-shu-de-jing-xiang-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

AC代码

# 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 root is None:
            return None
        else:
            root.right, root.left = self.mirrorTree(root.left), self.mirrorTree(root.right)
            return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14

唔，读完题半分钟秒了笔者也确实是没想到。。不过这题用递归真的都已经怼到脸上了，很快AC也很正常。

Python一行法

return TreeNode(root.val, self.mirrorTree(root.right), self.mirrorTree(root.left)) if root else None
1

简单题往往都能找到Python的一行秒杀方法，这题也不例外。不过从代码来看这种方法需要新建TreeNode的变量，相对来说可能比较费空间。直接root上改会好一丝。

官方题解之辅助栈

class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root: return
        stack = [root]
        while stack:
            node = stack.pop()
            if node.left: stack.append(node.left)
            if node.right: stack.append(node.right)
            node.left, node.right = node.right, node.left
        return root

作者：jyd
链接：https://leetcode.cn/problems/er-cha-shu-de-jing-xiang-lcof/solution/mian-shi-ti-27-er-cha-shu-de-jing-xiang-di-gui-fu-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这种方法算是利用栈的先进后出的特性，算一个启发叭，但本质来说和递归还是一样的，无非是遍历树的方法有所区别罢了。