面试题04.09.二叉搜索树序列

链接：面试题04.09.二叉搜索树序列
难度：Hard
标签：树、二叉搜索树、回溯、二叉树
简介：从左向右遍历一个数组，通过不断将其中的元素插入树中可以逐步地生成一棵二叉搜索树。给定一个由不同节点组成的二叉搜索树，输出所有可能生成此树的数组。

题解 1 - typescript

• 编辑时间：2021-08-07
• 执行用时：120ms
• 内存消耗：46.1MB
• 编程语言：typescript
• 解法介绍：递归生成左右子树，保证左右子树顺序不变。

function BSTSequences(root: TreeNode | null): number[][] {
  if (root === null) return [[]];
  if (root.left === null && root.right === null) return [[root.val]];
  if (root.left !== null && root.right === null) {
    const sub = BSTSequences(root.left);
    return sub.map(v => [root.val, ...v]);
  }
  if (root.right !== null && root.left === null) {
    const sub = BSTSequences(root.right);
    return sub.map(v => [root.val, ...v]);
  }
  const subl = BSTSequences(root.left);
  const subr = BSTSequences(root.right);
  const ans: number[][] = [];
  for (const l of subl) {
    for (const r of subr) {
      merge(l, 0, r, 0, [], root.val);
    }
  }
  return ans;
  function merge(
    l: number[],
    idxl: number,
    r: number[],
    idxr: number,
    list: number[],
    root: number
  ): void {
    if (l.length === idxl) {
      for (let i = idxr; i < r.length; i++) list.push(r[i]);
      list.unshift(root);
      ans.push(list);
      return;
    }
    if (r.length === idxr) {
      for (let i = idxl; i < l.length; i++) list.push(l[i]);
      list.unshift(root);
      ans.push(list);
      return;
    }
    merge(l, idxl + 1, r, idxr, [...list, l[idxl]], root);
    merge(l, idxl, r, idxr + 1, [...list, r[idxr]], root);
  }
}