剑指offer:重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
创新互联-专业网站定制、快速模板网站建设、高性价比西华网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式西华网站制作公司更省心,省钱,快速模板网站建设找我们,业务覆盖西华地区。费用合理售后完善,10余年实体公司更值得信赖。
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, preorder, inorder):
"""
与树有关的题目一般来讲可以先尝试使用递归方法求解。
:param preorder: 一棵树的先序遍历结果
:param inorder: 同一棵树的中序遍历结果
:return: 构造的树的根节点
"""
def helper(preorder_start, preorder_end, inorder_start, inorder_end):
"""
通过传下标代替传列表,可以减少中间的内存开销。
四个参数分别代表了当前子树的先序遍历和中序遍历的结果,根据这四个参数可以从总体的
先序遍历和中序遍历中找到当前子树的先序遍历和中序遍历。
:return: 当前子树的根节点
"""
# 对于一棵子树,其先序遍历的第一个节点就是根节点
root = TreeNode(preorder[preorder_start])
# 如果当前子树只有一个节点(这时这个子树其实是叶子节点),这是我们的递归出口
if preorder_start == preorder_end:
# 这里增加了一个输入合法性判断
if inorder_start == inorder_end \
and preorder[preorder_end] == inorder[inorder_end]:
return root
else:
return None
# 然后从中序遍历中找到这个根节点,按照中序遍历的顺序,根节点左边的是左子树的节点,
# 右边的是右子树的节点
i = inorder_start
while i <= inorder_end:
if inorder[i] == root.val:
break
i += 1
# 输入合法性判断,确保这个根节点在中序遍历中能找到
if inorder[i] != root.val:
return None
left_length = i - inorder_start # 左子树的节点数
# 左右子树的先序遍历下标
preorder_left_start = preorder_start + 1
preorder_left_end = preorder_left_start + left_length - 1
preorder_right_start = preorder_left_end + 1
preorder_right_end = preorder_end
# 左右子树的中序遍历的下标
inorder_left_start = inorder_start
inorder_left_end = i - 1
inorder_right_start = i + 1
inorder_right_end = inorder_end
# 如果存在左右子树,则递归下去
if left_length > 0:
root.left = helper(preorder_left_start, preorder_left_end,
inorder_left_start, inorder_left_end)
if left_length < preorder_end - preorder_start:
root.right = helper(preorder_right_start, preorder_right_end,
inorder_right_start, inorder_right_end)
return root
if not preorder or not inorder: # 验证输入合法性
return None
return helper(0, len(preorder) - 1, 0, len(inorder) - 1) # 递归构造二叉树
分享文章:剑指offer:重建二叉树
文章分享:http://hbruida.cn/article/picoij.html