18 二叉树的镜像

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像。

示例：

原树:     8
        / \
       6   10
      / \  / \
     5  7 9  11

镜像:    8
        / \
       10  6
      / \  / \
     11 9 7  5

解题思路

核心思想：递归交换每个节点的左右子树。

关键步骤：

1. 如果节点为空，返回
2. 交换节点的左右子树
3. 递归处理左子树和右子树

时间复杂度：O(n) 空间复杂度：O(n)（递归栈）

Python 实现

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# 方法一：递归
def mirror_tree(root):
    """
    二叉树的镜像（递归）
    """
    if not root:
        return None

    # 交换左右子树
    root.left, root.right = root.right, root.left

    # 递归处理子树
    mirror_tree(root.left)
    mirror_tree(root.right)

    return root


# 方法二：迭代（栈）
def mirror_tree_iterative(root):
    """
    二叉树的镜像（迭代，使用栈）
    """
    if not root:
        return None

    stack = [root]

    while stack:
        node = stack.pop()

        # 交换左右子树
        if node:
            node.left, node.right = node.right, node.left
            stack.append(node.left)
            stack.append(node.right)

    return root


# 方法三：层序遍历（队列）
def mirror_tree_level_order(root):
    """
    二叉树的镜像（层序遍历）
    """
    if not root:
        return None

    from collections import deque
    queue = deque([root])

    while queue:
        node = queue.popleft()

        # 交换左右子树
        if node:
            node.left, node.right = node.right, node.left
            queue.append(node.left)
            queue.append(node.right)

    return root


# 辅助函数：创建树
def build_tree(values, index=0):
    if index >= len(values) or values[index] is None:
        return None
    node = TreeNode(values[index])
    node.left = build_tree(values, 2 * index + 1)
    node.right = build_tree(values, 2 * index + 2)
    return node


# 辅助函数：中序遍历
def inorder_traversal(root):
    if not root:
        return []
    return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)


# 测试代码
if __name__ == "__main__":
    # 创建树
    values = [8, 6, 10, 5, 7, 9, 11]
    root = build_tree(values)

    print("原树中序遍历:", inorder_traversal(root))

    mirror_tree(root)
    print("镜像后中序遍历:", inorder_traversal(root))

# 输出:
# 原树中序遍历: [5, 6, 7, 8, 9, 10, 11]
# 镜像后中序遍历: [11, 10, 9, 8, 7, 6, 5]

图解

原树:
        8
       / \
      6   10
     / \  / \
    5  7 9  11

镜像过程（层序遍历）:

步骤1: 处理节点8
       交换左右 → 8的右是6，左是10
        8
       / \
      10  6

步骤2: 处理节点10
       交换左右 → 10的左是11，右是9
        8
       / \
      10  6
     / \
    11  9

步骤3: 处理节点6
       交换左右 → 6的左是7，右是5
        8
       / \
      10  6
     / \  / \
    11 9 7  5

最终镜像完成!