题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
- 数据结构：
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
# 根节点构建
node=TreeNode(0)
node.val=pre[0]
# 当前根节点对应的中序数组的索引
id=tin.index(pre[0])
# 左右子树都为0时，返回当前节点。注意 and or逻辑区分
if id-1<0 and id+1>len(tin)-1:
return node
# 左子树不为空时，注意python右区间表达需要+1
if id-1>=0:
node.left=self.reConstructBinaryTree(pre[1:id+1],tin[:id])
# 右子树不为空时
if id+1<=len(tin)-1:
node.right=self.reConstructBinaryTree(pre[id+1:],tin[id+1:])
return node
