重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路

前序遍历的顺序为根左右。中序遍历的顺序为左根右。前序里的第一个元素正好在中序里把数组划分为左右子树。按照这个思想递归的把树的左右子树找到。
在中序中找到根节点的所在位置，作为index。index之前为左子树。index之后为右子树。同时index的长度应用到前序中也可以把前序里的左右子树找到（除去根之后的index个结点为左子树的结点）。
下一步就是递归的寻找左右子树，然后找到最底层返回单个的根结点作为结果。

代码

class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        if not pre or not tin:
            return None
        root = TreeNode(pre.pop(0))
        index = self.findIndex(root,tin)
        root.left = self.reConstructBinaryTree(pre[:index],tin[:index])
        root.right = self.reConstructBinaryTree(pre[index:],tin[index+1:])
        return root
    def findIndex(self,root,tin):
        for i in range(len(tin)):
            if tin[i] == root.val:
                return i
        return 0