class TreeNode:def __init__(self,data,left,right):self.data=dataself.left=left
self.right=right
方法１
def construct_tree(pre_order,mid_order):
##保证结点数不为０，该树才能重构
if (len(pre_order)==0) or (len(mid_order)==0):
return None
##根节点即为前序遍历的首元素
root_data=pre_order[0]# make sure the root_Data
##若结点个数为１，则不含左右子书
if len(pre_order)==1 :
return TreeNode(root_data,None,None)
##在中序遍历中查找根节点，确定其下标
for i in range(len(mid_order)):if root_data==mid_order[i]:breakroot_mid_index=i
#if root_mid_index >0:
＃＃分别重构其左右子书
left=construct_tree(pre_order[1:root_mid_index+1],mid_order[:root_mid_index])if root_mid_index<len(mid_order):right=construct_tree(pre_order[root_mid_index+1:],mid_order[root_mid_index+1:])return TreeNode(root_data,left,right)if __name__=='__main__':pre_order = [1, 2, 4, 7, 3, 5, 6, 8]mid_order = [4, 7, 2, 1, 5, 3, 8, 6]
root=construct_tree(pre_order,mid_order)
方法２
#def reConstructBinaryTree(pre, tin):# # write code here# if (len(pre) == 0) or (len(tin) == 0):# return None## rootValue = pre[0]# root = TreeNode(rootValue,None,None)# if len(pre)==1:# return root# rootTinIndex = 0# for i in range(len(tin)):# if tin[i] == rootValue:#rootTinIndex = i# preStart = 1# preEnd = rootTinIndex+1# tinStart = 0# tinEnd = rootTinIndex
# if rootTinIndex > 0:
＃＃用递归函数返回的结果赋值给某个变量该变量之前必须定义过初值，如root.left/right==None
# root.left = reConstructBinaryTree(pre[preStart:preEnd], tin[tinStart:tinEnd])# if rootTinIndex < len(pre):# root.right = reConstructBinaryTree(pre[preEnd:], tin[tinEnd+1:])# return root#if __name__=='__main__':# pre = [1, 2, 4, 7, 3, 5, 6, 8]# tin = [4, 7, 2, 1, 5, 3, 8, 6]# root=reConstructBinaryTree(pre,tin)print root.dataprint root.left.data,root.right.dataprint root.left.left.data,root.right.left.data,root.right.right.dataprint root.left.left.right.data,root.right.right.left.data
附件列表
如果觉得《面试题６－－利用前序和中序遍历重构二叉树－－递归方法》对你有帮助，请点赞、收藏，并留下你的观点哦！
