95.不同的二叉搜索树II

链接：95.不同的二叉搜索树II
难度：Medium
标签：树、二叉搜索树、动态规划、回溯、二叉树
简介：给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。

题解 1 - typescript

• 编辑时间：2020-07-21
• 执行用时：108ms
• 内存消耗：45.8MB
• 编程语言：typescript
• 解法介绍：递归遍历。

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
function generateTrees(n: number): Array<TreeNode | null> {
  if (n === 0) return [];
  return _genTrees(1, n);
  function _genTrees(start: number, end: number): Array<TreeNode | null> {
    const trees: Array<TreeNode | null> = [];
    if (start > end) {
      trees.push(null);
      return trees;
    }
    for (let i = start; i <= end; i++) {
      const lefts = _genTrees(start, i - 1);
      const rights = _genTrees(i + 1, end);
      for (const left of lefts) {
        for (const right of rights) {
          const tree = new TreeNode(i);
          tree.left = left;
          tree.right = right;
          trees.push(tree);
        }
      }
    }
    return trees;
  }
}

题解 2 - typescript

• 编辑时间：2021-05-07
• 执行用时：112ms
• 内存消耗：46MB
• 编程语言：typescript
• 解法介绍：递归左右子树。

function generateTrees(n: number): Array<TreeNode | null> {
  const createTree = (startNum: number, endNum: number): (TreeNode | null)[] => {
    const ans: TreeNode[] = [];
    if (startNum > endNum) return [null];
    for (let i = startNum; i <= endNum; i++) {
      const leftList = createTree(startNum, i - 1);
      const rightList = createTree(i + 1, endNum);
      for (const left of leftList) {
        for (const right of rightList) {
          const node = new TreeNode(i, left, right);
          ans.push(node);
        }
      }
    }
    return ans;
  };
  return createTree(1, n);
}