实现二叉树镜像
1 问题
二叉树镜像：二叉树所有非叶子结点且同时存在左右子结点，将其左右子结点互换位置则得到其镜像的二叉树，如果只存在一个子结点则不互换。那么该如何用python代码实现二叉树的镜像转换？
2 方法
- 先序遍历原二叉树的每个结点，如果遍历到的结点有子结点，就交换它的两个子结点。
- 递归遍历每个结点的子结点，同样，如果遍历到的子结点有子结点，就交换它的两个子结点。
代码清单 1
# 定义结点
class Node(object):
value = None
left = None
right = None
def __init__(self, value, left, right):
value = value
left = left
right = right
# 镜像反转左右字结点
def mirror_recursively(node: Node):
if node is None or (node.left is None and node.right):
return
node.left, node.right = node.right, node.left
if node.left:
mirror_recursively(node.left)
if node.right:
mirror_recursively(node.right)3 结语
可以总结出这两棵树的根结点相同，但它们的左、右两个子结点交换了位置。所以我们可以得出求一棵树的镜像的过程:先先序遍历这棵树的每个结点，如果遍历到的结点有子结点，就交换它的两个子结点。当交换完所有非叶结点的左、右子结点之后，就得到了树的镜像。此次实验中，运用了所学的二叉树的基本结构、遍历等知识并运用到实际操作中。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2024-02-28，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
