用前序和中序重建二叉树 python
2021-05-15 15:27
标签：dex 方法 python版本 app tin turn 包含 rom 位置 程序实现了用二叉树的前序遍历序列和中序遍历序列重建二叉树，代码用python实现。 首先定义二叉树节点的类： 二叉树的重建采用递归完成，具体原理比较简单，不做阐述 可以采用层序输出的方式验证生成的二叉树是否正确，用先进先出的队列依次保存层序遍历到的节点（该方法在类Solution下） python版本：3.6 用前序和中序重建二叉树 python 标签：dex 方法 python版本 app tin turn 包含 rom 位置 原文地址：https://www.cnblogs.com/bambipai/p/9750712.html1 class TreeNode:
2 def __init__(self, x):
3 self.val = x
4 self.left = None
5 self.right = None
1 class Solution:
2 def reConstructBinaryTree(self, pre, tin):#pre、tin分别是前序序列和中序序列
3 # write code here
4 if len(pre)>0:
5 root=TreeNode(pre[0])#前序序列的第一个肯定是当前子树的根节点
6 rootid=tin.index(root.val)#通过根节点在中序序列中的位置划分出左右子树包含的节点
7 root.left=self.reConstructBinaryTree(pre[1:1+rootid],tin[:rootid])#重建左子树
8 root.right=self.reConstructBinaryTree(pre[1+rootid:],tin[rootid+1:])#重建右子树
9 return root
def PrintFromTopToBottom(self, root):
ans=[]
if root==None:
return ans
else:
q=[root]
while q:
node=q.pop(0)
ans.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return ans
文章标题：用前序和中序重建二叉树 python
文章链接：http://soscw.com/index.php/essay/85837.html