如何通过递归实现二叉树翻转?附建树代码与伪代码
基于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
相关产品推荐
相关产品推荐

