力扣链接：105.从前序与中序遍历序列构造二叉树

难度：⭐⭐

解题关键词：二叉树

解题思路：根据前序序列拿到根节点，然后基于根节点去切割中序序列，得到左右子树，然后拿左子树的 size 去切割前序序列，之后使用递归创建根节点的左右子树即可。

function buildTree(preOrder: number[], inOrder: number[]): TreeNode | null {
  // 如果前序序列为空，直接返回 null
  if (!preOrder.length) return null;

  // 找到根节点
  const mid = preOrder[0];

  // 创建根节点
  const root = new TreeNode(mid);

  // 找到根节点在中序序列中位置，然后基于这个位置取切割数组
  const midIndexInInOrder = inOrder.findIndex((item) => item === mid);
  // 根节点左子树的中序序列
  const leftInOrder = inOrder.slice(0, midIndexInInOrder);
  // 根节点右子树的中序序列
  const rightInOrder = inOrder.slice(midIndexInInOrder + 1);

  // 根节点左子树的前序序列
  const leftPreOrder = preOrder.slice(1, 1 + leftInOrder.length);
  // 根节点右子树的前序序列
  const rightPreOrder = preOrder.slice(1 + leftInOrder.length);

  // 递归创建根节点的左右子树
  root.left = buildTree(leftPreOrder, leftInOrder);
  root.right = buildTree(rightPreOrder, rightInOrder);

  return root;
}