leetcode原题链接：剑指 Offer 07. 重建二叉树
二叉树前序遍历的顺序为：
先遍历根节点；
随后递归地遍历左子树；
最后递归地遍历右子树。
二叉树中序遍历的顺序为：
先递归地遍历左子树；
随后遍历根节点；
最后递归地遍历右子树。
在「递归」地遍历某个子树的过程中，是将这颗子树看成一颗全新的树，按照上述的顺序进行遍历。挖掘「前序遍历」和「中序遍历」的性质，就可以得出本题的做法。
# 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 myBuildTree(preorder_left, preorder_right, inorder_left, inorder_right):
if preorder_left > preorder_right:
return None
preorder_root = preorder_left
inorder_root = index[preorder[preorder_root]]
root = TreeNode(preorder[preorder_root])
size_left_subtree = inorder_root - inorder_left
root.left = myBuildTree(preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1)
root.right = myBuildTree(preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right)
return root
n = len(preorder)
index = {element: i for i, element in enumerate(inorder)}
return myBuildTree(0, n - 1, 0, n - 1)
复杂度分析
时间复杂度：
O
(
N
)
O(N)
O(N)，其中
n
n
n 是树中的节点个数。
空间复杂度：
O
(
N
)
O(N)
O(N)，需要使用
O
(
N
)
O(N)
O(N)的空间存储哈希映射，以及
O
(
h
)
O(h)
O(h)（其中
h
h
h 是树的高度）的空间表示递归时栈空间。这里
h
h
h <
n
n
n，所以总空间复杂度为
O
(
N
)
O(N)
O(N)。