1008.前序遍历构造二叉搜索树

链接：1008.前序遍历构造二叉搜索树
难度：Medium
标签：栈、树、二叉搜索树、数组、二叉树、单调栈
简介：返回与给定前序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。

题解 1 - typescript

• 编辑时间：2021-08-07
• 执行用时：72ms
• 内存消耗：39.6MB
• 编程语言：typescript
• 解法介绍：获取左子树和右子树分别构造。

function bstFromPreorder(preorder: number[]): TreeNode | null {
  const n = preorder.length;
  if (n === 0) return null;
  const mid = preorder[0];
  let i = 1;
  while (i < n && preorder[i] < mid) i++;
  return new TreeNode(
    mid,
    bstFromPreorder(preorder.slice(1, i)),
    bstFromPreorder(preorder.slice(i))
  );
}