输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

3

限制：

0 <= 节点个数 <= 5000

注意：本题与主站105题重复

# 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, inorder):

解题思路：

前序遍历性质：节点按照[根节点|左子树|右子树]排序。

中序遍历性质：节点按照[左子树|根节点|右子树]排序。

以题目示例为例：

• 前序遍历划分[3|9|20 15 7]
• 中序遍历划分[9|3|15 20 7]

根据以上性质，可得出以下推论：

1. 前序遍历的首元素为树的根节点node的值。
2. 在中序遍历中搜索根节点node的索引，可将中序遍历划分为[左子树|根节点|右子树]。
3. 根据中序遍历中的左(右)子树的节点数量，可将前序遍历划分为[根节点|左子树|右子树]。

以上子树的递推性质是分治算法的体现，考虑通过递归对所有子树进行划分。

分治算法解析：

• 递推参数：根节点在前序遍历的索引root、子树在中序遍历的左边界left、子树在中序遍历的右边界right;

• 终止条件：当left>right，代表已经越过叶节点，此时返回null;

• 递推公式：

  1. 建立根节点node：节点值为preorder[root];
  2. 划分左右子树：查找根节点在中序遍历inorder中的索引i;

  为了提升效率，本文使用哈希表dic存储中序遍历的值与索引的映射，查找操作的时间复杂度为$O(1)$。

  1. 构建左右子树：开启左右子树递归：
     • 返回值：回溯返回node，作为上一层递归中根节点的左/右节点；

复杂度分析：

• 时间复杂度$O(N)$：其中$N$为树的节点数量。初始化HashMap需遍历inorder，占用$O(N)$。递归共建立N个节点，每层递归中的节点建立，搜索操作占用$O(1)$，因此使用$O(N)$时间。
• 空间复杂度$O(N)$：HashMap使用$O(N)$额外空间。最差情况下，树退化为链表，递归深度达到N，占用$O(N)$额外空间；最好情况下，树为满二叉树，递归深度为$logN$，占用$O(logN)$额外空间。

代码：

注意：本文方法只适用于”无重复节点值”的二叉树。

class Solution:
    def buildTree(self, preorder, inorder):
        def recur(root, left, right):
            if left > right: return  # 递归终止
            node = TreeNode(preorder[root]) # 建立根节点
            i = dic[preorder[root]] # 划分根节点，左子树，右子树
            node.left = recur(root+1, left, i-1) # 开启左子树递归
            node.right = recur(i-left+root+1,i+1,right) # 开启右子树递归
            return node # 回溯返回根节点
        dic, preorder = {}, preorder
        for i in range(len(inorder)):
            dic[inorder[i]] = i
       	return recur(0,0,len(inorder)-1)