类型：树
-
重建二叉树 💛
https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
❓ 已知一棵树的前序遍历和中序遍历数组，构造出这棵二叉树。
💡 递归
对于任意一颗树而言，前序遍历的形式总是：
[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]而中序遍历的形式总是：
[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]据此，我们可以递归地构造出二叉树。
我们可以使用哈希来帮助我们快速定位出根结点在中序遍历数组中的位置。
class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: def myBuildTree(preorder_left: int, preorder_right: int, inorder_left: int, inorder_right: int): 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 # 递归地构造左子树，并连接到根节点 # 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素 root.left = myBuildTree(preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1) # 递归地构造右子树，并连接到根节点 # 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+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)
💡 迭代
迭代的方法比较巧妙，且不易表述。具体可以参见官方题解。