题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
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) # 递归构造二叉树另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
