题目链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
难度：中等

描述：
给定两个整数数组 preorder 和 inorder，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

提示：
preorder和inorder中无重复元素。

题解

preorder中的第一个值是根节点root，找到root在inorder中的位置就可以找到root左子树和右子树的大小。那么就可以找到root左子树和右子树在preorder中的分布。

root left_subtree right_subtree
left_subtree root right_subtree 
  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
  9.         def recursion(p_left, p_right, i_left, i_right):
  10.             if p_left > p_right:
  11.                 return None
  13.             p_root_idx = p_left
  14.             i_root_idx = hm[preorder[p_root_idx]]
  15.             left_size = i_root_idx - i_left
  16.             root = TreeNode(val=preorder[p_root_idx])
  17.             root.left = recursion(p_left+1, p_left+left_size, i_left, i_root_idx-1)
  18.             root.right = recursion(p_left+left_size+1, p_right, i_root_idx+1, i_right)
  19.             return root
  21.         length = len(preorder)
  22.         hm = {}
  23.         for i in range(length):
  24.             hm[inorder[i]] = i
  26.         return recursion(0, length-1, 0, length-1)