【题目描述】
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
【思路】
前序遍历中第一个数为根节点,在中序遍历中寻找到根节点之后,可区分左右子树,便可递归构建左右子树
注意边界条件判断
1.若前序、中序为空,则二叉树为NULL
2.递归时,若只剩一个节点,则该节点即为根节点,退出递归调用。
【代码】
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
# write code here
def ConstructBinaryNode(pre,tin):
tinlen = len(tin)
rootvalue = pre[0]
root = TreeNode(rootvalue)
if tinlen==1:
return root
#在中序遍历中寻找根节点
leftlength = 0
while leftlength<tinlen and tin[leftlength]!=rootvalue:
leftlength+=1
#构建左子树
if leftlength>0:
root.left = ConstructBinaryNode(pre[1:leftlength+1],tin[0:leftlength])
#构建右子树
if tinlen-leftlength>=2:
root.right = ConstructBinaryNode(pre[leftlength+1:],tin[leftlength+1:])
return root
prelen = len(pre)
tinlen = len(tin)
#树为空判断
if prelen==0 or tinlen==0:
return NULL
return ConstructBinaryNode(pre,tin)
网友评论