# -*- encoding: utf-8 -*-
"""
@File    : prac105.py
@Time    : 2020/5/22 10:12 下午
@Author  : zhengjiani
@Email   : 936089353@qq.com
@Software: PyCharm
使用哈希映射快速的定位根节点，哈希映射中的每个键值对，键表示一个元素（节点的值），值表示在中序遍历中出现的位置
构造二叉树的过程之前，可以通过一次扫描构造出哈希映射，此后只需要O(1)的时间就可以对根节点进行定位了
"""
# Definition for a binary tree node.
from typing import List


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def myBuildTree(preorder_left:int,preorder_right:int,inorder_left:int,inorder_right:int):
            if preorder_left > preorder_right:
                return None
            # 前序遍历的第一个节点就是根节点
            preorder_root = preorder_left
            # 在中序遍历中定位根节点
            inorder_root = inorder.index(preorder[preorder_root])
            # 先建立根节点
            root = TreeNode(preorder[preorder_root])
            # 得到左子树中节点数目
            size_left_subtree = inorder_root - inorder_left
            # 递归的构造左子树并连接根节点
            # 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
            root.left = myBuildTree(preorder_left+1,preorder_left+size_left_subtree,inorder_left,inorder_root-1)
            # 递归的构造右子树并连接根节点
            # 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
            root.right = myBuildTree(preorder_left+size_left_subtree+1,preorder_root,inorder_root+1,inorder_right)
            return root

        n = len(preorder)
        # 构造哈希映射，快速定位节点
        index = {element:i for i,element in enumerate(inorder)}
        return myBuildTree(0,n-1,0,n-1)














