不同的二叉搜索树 II

[louzhedong]

习题

出处：LeetCode 算法第95题

给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。

示例:

输入: 3
输出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

思路

动态规划

解答

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function (n) {
  if (n === 0) return [];
  var dp = new Array(n + 1).fill(undefined).map(function () { return [] });
  dp[0].push(null);

  for (var i = 1; i <= n; i++) {
    for (var l = 0; l < i; l++) {
      var r = i - 1 - l;
      dp[l].forEach(function (left) {
        dp[r].forEach(function (right) {
          var root = new TreeNode(l + 1)
          root.left = left;
          root.right = cloneTree(right, l + 1);
          dp[i].push(root);
        })
      })
    }
  }
  return dp[n];
};

function cloneTree(root, offset) {
  if (!root) {
    return null;
  }

  const result = new TreeNode(root.val + offset);
  result.left = cloneTree(root.left, offset);
  result.right = cloneTree(root.right, offset);
  return result;
}