您的位置:首页 > 脚本大全 > > 正文

python二叉树是怎么来的(Python二叉树的镜像转换实现方法示例)

更多 时间:2022-01-14 02:47:51 类别:脚本大全 浏览量:1250

python二叉树是怎么来的

Python二叉树的镜像转换实现方法示例

本文实例讲述了python二叉树的镜像转换实现方法。分享给大家供大家参考,具体如下:

问题描述

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

python二叉树是怎么来的(Python二叉树的镜像转换实现方法示例)

思路描述

1. 代码比文字更直观

2. 文字描述:新建一个二叉树,利用递归法,将源二叉树上的左节点赋值到新二叉树的右节点,将源二叉树上的右节点赋值到新二叉树的左节点。

python代码

  • ?
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • # 方式1:生成新的镜像二叉树
  • def getmirrorbst(self, root):
  •   if root == none:
  •     return
  •   newtree = treenode(root.val)
  •   newtree.right = self.getmirrorbst(root.left)
  •   newtree.left = self.getmirrorbst(root.right)
  •   return newtree
  • 但是提交代码后,说通过率为0… 原来要求将原有的二叉树就地改成镜像二叉树…如此一来,代码就更简单了:因为交换根节点的左右子节点时,以左右子节点为根节点的左子树和右子树也会交换位置。最终的python代码如下:

  • ?
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • # 方式2:改变给定的二叉树为镜像二叉树
  • def turntomirror(self, root):
  •   if root == none:
  •     return
  •   root.right, root.left = root.left, root.right
  •   self.turntomirror(root.left)
  •   self.turntomirror(root.right)
  •   return root
  • 包含测试代码的最终代码如下:

  • ?
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • class solution:
  •   # 给定一个二叉树,获得其镜像(轴对称)的镜像二叉树:
  •   # 方式1:生成新的镜像二叉树
  •   def getmirrorbst(self, root):
  •     if root == none:
  •       return
  •     newtree = treenode(root.val)
  •     newtree.right = self.getmirrorbst(root.left)
  •     newtree.left = self.getmirrorbst(root.right)
  •     return newtree
  •   # 方式2:改变给定的二叉树为镜像二叉树
  •   def turntomirror(self, root):
  •     if root == none:
  •       return
  •     root.right, root.left = root.left, root.right
  •     self.turntomirror(root.left)
  •     self.turntomirror(root.right)
  •     return root
  •   # 给定二叉树的前序遍历和中序遍历,获得该二叉树
  •   def getbstwithpretin(self, pre, tin):
  •     if len(pre)==0 | len(tin)==0:
  •       return none
  •     root = treenode(pre[0])
  •     for order,item in enumerate(tin):
  •       if root .val == item:
  •         root.left = self.getbstwithpretin(pre[1:order+1], tin[:order])
  •         root.right = self.getbstwithpretin(pre[order+1:], tin[order+1:])
  •         return root
  • class treenode:
  •   def __init__(self, x):
  •     self.left = none
  •     self.right = none
  •     self.val = x
  • if __name__ == '__main__':
  •   flag = "turntomirror"
  •   solution = solution()
  •   preorder_seq = [1, 2, 4, 7, 3, 5, 6, 8]
  •   middleorder_seq = [4, 7, 2, 1, 5, 3, 8, 6]
  •   treeroot1 = solution.getbstwithpretin(preorder_seq, middleorder_seq)
  •   if flag == "mirrorbst":
  •     newroot = solution.getmirrorbst(treeroot1)
  •     print(newroot)
  •   if flag == "turntomirror":
  •     solution.turntomirror(treeroot1)
  •     print(treeroot1)
  • 希望本文所述对大家python程序设计有所帮助。

    原文链接:https://blog.csdn.net/u010005281/article/details/79473690

    您可能感兴趣