【剑指offer】重建二叉树（python）

记住没有中序遍历结果是不能重建二叉树的！

1. 二叉树的左中后遍历顺序。
   前序遍历：根结点 ---> 左子树 ---> 右子树
   中序遍历：左子树---> 根结点 ---> 右子树
   后序遍历：左子树 ---> 右子树 ---> 根结点
   前序遍历：1 2 4 5 7 8 3 6
   中序遍历：4 2 7 5 8 1 3 6
   后序遍历：4 7 8 5 2 6 3 1
2. 根据前序和中序遍历重建二叉树。
   前序中第一位是根节点，在中序中定位出根节点，左边就是左子树，右边是右子树，得到左子树的长度后，在前序序列中确认左子树的序列，第一位定位到左子树的根节点，继续在中序中定位出根节点，分出左右子树，持续递归。递归结束条件是序列为空。
   关键在于从前序遍历序列中得到根节点，从而在中序遍历序列中得到左子树长度，进一步在前序序列中定位到左子树及其根节点位置。

   # -*- coding:utf-8 -*-
   # class TreeNode:
   #     def __init__(self, x):
   #         self.val = x
   #         self.left = None
   #         self.right = None
   class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        if len(pre)==0:return None
        root=ListNode(pre[0])
        pos=tin.index(pre[0])
        root.left=self.reConstructBinaryTree(pre[1:pos+1], tin[:pos])
        root.right=self.reConstructBinaryTree(pre[pos+1:],tin[pos+1:])
        return root