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

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

提示：
长度：[1, 3000]
preorder与inorder中无重复元素

题解

  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.         # preorder: [root | left | right]
  10.         # inorder : [left | root | right]
  11.         m = {}
  12.         for i in range(len(inorder)):
  13.             m[inorder[i]] = i
  15.         def recursion(p_left, p_right, i_left, i_right):
  16.             if p_left > p_right:
  17.                 return None
  19.             preorder_root_index = p_left
  20.             inoredr_root_index = m[preorder[preorder_root_index]]
  21.             left_length = inoredr_root_index - i_left
  23.             root = TreeNode(preorder[preorder_root_index])
  24.             root.left = recursion(p_left+1, p_left+left_length, i_left, inoredr_root_index-1)
  25.             root.right = recursion(p_left+left_length+1, p_right, inoredr_root_index+1, i_right)
  26.             return root
  28.         return recursion(0, len(preorder)-1, 0, len(inorder)-1)