Python递归实现二叉树的镜像算法

2023-04-15 00:00:00 算法 镜像 递归

二叉树的镜像指的是将二叉树中每个节点的左右子树交换位置，得到一个新的二叉树。

递归实现二叉树的镜像算法的基本思路是：

  1. 交换当前节点的左右子节点位置。
  2. 递归处理当前节点的左子节点，得到其对应的镜像树。
  3. 递归处理当前节点的右子节点，得到其对应的镜像树。
  4. 将当前节点的左右子节点替换为步骤2步和步骤3得到的左右子树。

代码演示如下：

# 定义二叉树节点结构体
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def mirror_binary_tree(root):
    # 递归出口：当节点为 None 时直接返回
    if not root:
        return

    # 交换当前节点的左右子节点位置
    root.left, root.right = root.right, root.left

    # 递归处理当前节点的左子节点，得到其对应的镜像树
    mirror_binary_tree(root.left)

    # 递归处理当前节点的右子节点，得到其对应的镜像树
    mirror_binary_tree(root.right)

    # 将当前节点的左右子节点替换为步骤2步和步骤3得到的左右子树
    return root

# 创建一个二叉树，并打印其先序遍历
def preorder_traversal(root):
    if not root:
        return
    print(root.val, end=' ')
    preorder_traversal(root.left)
    preorder_traversal(root.right)

if __name__ == '__main__':
    # 构建二叉树
    root = TreeNode('pidancode.com')
    root.left = TreeNode('is')
    root.right = TreeNode('awesome')
    root.left.left = TreeNode('Python')
    root.left.right = TreeNode('programming')
    root.right.left = TreeNode('language')
    root.right.right = TreeNode('!')

    # 输出原二叉树先序遍历
    print('原二叉树先序遍历：', end='')
    preorder_traversal(root)
    print()

    # 获取二叉树的镜像
    mirror_root = mirror_binary_tree(root)

    # 输出镜像二叉树先序遍历
    print('镜像二叉树先序遍历：', end='')
    preorder_traversal(mirror_root)
    print()

运行结果：

原二叉树先序遍历：pidancode.com is Python programming awesome language !
镜像二叉树先序遍历：pidancode.com awesome language ! is programming Python

相关文章