leetcode原题链接：剑指 Offer 27. 二叉树的镜像
根据二叉树镜像的定义, 考虑递归遍历
d
f
s
\mathrm{dfs}
dfs 二叉树，交换每个节点的左 / 右子节点, 即可生成 二叉树的镜像。
递归解析：
# 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
root.left, root.right = self.mirrorTree(root.right), self.mirrorTree(root.left)
return root 复杂度分析：
时间复杂度：
O
(
N
)
O(N)
O(N)，其中
N
N
N 为二叉树的节点数量, 建立二叉树镜像需要遍历树的所有节点, 占 用
O
(
N
)
O(N)
O(N) 时间。
空间复杂度：
O
(
N
)
O(N)
O(N)，最差情况下
(
(
( 当二叉树退化为链表
)
,
),
), 递归时系统需使用
O
(
N
)
O(N)
O(N) 大小的栈空间。