前序、中序构建树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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