95.js

/** ------------------------------------------------------------------------------
 * 
 * 95. Unique Binary Search Trees II
 * Topics: Binary Tree, DP
 * https://leetcode.com/problems/unique-binary-search-trees-ii/description/
 * 
 ------------------------------------------------------------------------------ */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function (n) {
  function allPossibleBST(start, end, memo) {
    let res = []
    if (start > end) {
      res.push(null)
      return res
    }

    let key = start + "," + end
    if (memo[key] != undefined) return memo[key]

    for (let i = start; i <= end; i++) {
      let leftPossibleBST = allPossibleBST(start, i - 1, memo)
      let rightPossibleBST = allPossibleBST(i + 1, end, memo)
      for (let j = 0; j < leftPossibleBST.length; j++) {
        for (let k = 0; k < rightPossibleBST.length; k++) {
          let root = new TreeNode(i, leftPossibleBST[j], rightPossibleBST[k])
          res.push(root)
        }
      }
    }
    memo[key] = res
    return res
  }

  let memo = {}
  return allPossibleBST(1, n, memo)
}

/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function (n) {
  if (n === 0) {
    return []
  }

  const memo = new Map()

  function generateTreesHelper(start, end) {
    if (memo.has(`${start}-${end}`)) {
      return memo.get(`${start}-${end}`)
    }

    const trees = []
    if (start > end) {
      trees.push(null)
      return trees
    }

    for (let rootVal = start; rootVal <= end; rootVal++) {
      const leftTrees = generateTreesHelper(start, rootVal - 1)
      const rightTrees = generateTreesHelper(rootVal + 1, end)

      for (const leftTree of leftTrees) {
        for (const rightTree of rightTrees) {
          const root = new TreeNode(rootVal)
          root.left = leftTree
          root.right = rightTree
          trees.push(root)
        }
      }
    }

    memo.set(`${start}-${end}`, trees)
    return trees
  }

  return generateTreesHelper(1, n)
}