You need to enable JavaScript to run this app. 如何通过递归实现二叉树翻转?附建树代码与伪代码
优惠活动
大模型
产品
解决方案
定价
更多

如何通过递归实现二叉树翻转?附建树代码与伪代码

基于Python binarytree库的递归二叉树翻转实现

已编写的二叉树创建代码

from binarytree import build

# 按层序排列的节点值列表
nodes = [4, 2, 7, 1, 3, 6, 9]
# 构建初始完全二叉树
binary_tree = build(nodes)
print('初始二叉树结构:\n', binary_tree)
print('初始二叉树层序节点值:', binary_tree.values)

代码运行后会生成根节点为4,左子树以2为根、右子树以7为根的标准完全二叉树,binarytree库会自动以ASCII图形打印树结构,同时可通过.values属性读取层序遍历的节点值列表。

递归翻转核心实现步骤

对应梳理的伪代码,修正参数设计后的执行逻辑如下:

  • 递归终止判断:当遍历到的当前节点为空(即到达叶子节点的空指针位)时,直接结束当前分支的递归
  • 节点层交换:对当前有效节点,直接交换其指向的左子节点、右子节点引用
  • 左子树递归:对交换完成后的左子节点,执行整套翻转逻辑
  • 右子树递归:对交换完成后的右子节点,执行整套翻转逻辑

注:无需在递归函数中额外传递节点列表参数,binarytree库的节点对象携带完整的子节点引用,单独传入当前待处理节点即可完成全树遍历。

完整可运行代码

from binarytree import build

def invert_tree(current_node):
    # 递归终止:空节点直接返回
    if not current_node:
        return
    # 交换左右子节点引用
    current_node.left, current_node.right = current_node.right, current_node.left
    # 递归处理左右子树
    invert_tree(current_node.left)
    invert_tree(current_node.right)
    # 返回修改后的根节点,方便链式调用
    return current_node

# 构建初始树
nodes = [4, 2, 7, 1, 3, 6, 9]
binary_tree = build(nodes)
print('初始二叉树:\n', binary_tree)
print('初始层序值:', binary_tree.values)

# 执行翻转
invert_tree(binary_tree)

# 输出翻转结果
print('\n翻转后二叉树:\n', binary_tree)
print('翻转后层序值:', binary_tree.values)

输出方式说明

由于递归过程中是直接修改原树节点的左右指针引用,不会生成独立的新树结构,翻转完成后直接复用创建阶段的输出方式即可:

  • 直接打印树对象,会自动输出翻转后的ASCII树结构
  • 读取树对象的.values属性,即可得到翻转后的层序节点值列表,本例中翻转后的层序值为[4, 7, 2, 9, 6, 3, 1]

内容的提问来源于stack exchange,提问作者Maximilian Freitag

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.14 00:06:04