题目链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
难度：中等

描述：
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

题解

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