一、题目
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树：
3
/ \
9 20
/ \
15 7限制：
0 <= 节点个数 <= 5000
注意：本题与主站105题重复：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
二、思路
1. 递归
首先，分别看一下先序遍历与中序遍历是如何遍历的：
- 先序遍历：
根 > 左 > 右
- 中序遍历：
左 > 根 > 右
好了，通过先序遍历的遍历方式我们便可以知道先序遍历的结果中，第一个元素便是这个二叉树的根节点值，那么如果在中序遍历中找到这个节点，那我们就可以以这个根节点为分割点将中序遍历的结果分割开来，左边的便是该二叉树的左子树中序遍历结果，右边便是右子树。
因此我们根据中序遍历中的子树元素个数然后在先序遍历中进行对照，在先序遍历中找出左右子树的元素。我们便可以通过递归的方式构造出左右子树。
三、代码
1. 递归
# Definition for a binary tree node.
# 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 recursion(preorder_left, preorder_right, inorder_left):
“”“
:preorder_left: 当前二叉树在先序遍历结果中的左边界，也就是当前的先序遍历中的位置
:preorder_right: 当前二叉树在先序遍历结果中的右边界
:inorder_left: 当前子树在中序遍历中的左边界
“”“
if preorder_left > preorder_right:
return None
# 先序遍历的第一个元素便是根
root_val = preorder[preorder_left]
# 创建根节点
root = TreeNode(root_val)
# 获取中序遍历中根节点的下标
inorder_root_index = hash_inorder[root_val]
# 获得左子树元素个数
left_sum = inorder_root_index - inorder_left
root.left = recursion(preorder_left + 1, preorder_left + left_sum, inorder_left)
root.right = recursion(preorder_left + left_sum + 1, preorder_right, inorder_root_index + 1)
return root
# 对中序遍历建立哈希索引, 提高索引速度
hash_inorder = {element: index for index, element in enumerate(inorder)}
# 中序遍历与前序遍历的长度是一样的
n = len(preorder)
return recursion(0, n-1, 0)四、表现
| method | 运行时间 | 表现 | 内存消耗 | 表现 |
|---|---|---|---|---|
| 1. 递归 | 44ms | 98.60% | 18.5MB | 65.53% |
