不同的二叉搜索树II

二 题目

给定一个整数 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * 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) {
    
};

根据上面的已知函数，小伙伴们可以先尝试破解本题，确定了自己的答案后再看下面代码。

三 解题思路

动态规划：

/**
 * 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 buildTree(start, end) {
    let _result = []
    // 指针交错递归终止
    if (start > end) return [null]
    // i指针滑动，枚举left和right分段的所有可能
    for (let i = start; i <= end; i++) {
      // 左侧和右侧生成树的集合 返回为数组
      let left = buildTree(start, i - 1)
      let right = buildTree(i + 1, end)
      // 循环左右两侧的树集合 分别拼接到新树上，并且存储到结果数组中
      for (const leftNode of left) {
        for (const rightNode of right) {
          let node = new TreeNode(i)
          node.left = leftNode
          node.right = rightNode
          _result.push(node)
        }
      }
    }
    // 返回指定范围生成的树集合
    return _result
  }
  // n 为 0 是返回[]
  if (n === 0) return []
  // 指定最大范围
  return buildTree(1, n)
}

四 统计分析

本题不需要统计分析。

五 套路分析

如果小伙伴有更好的思路想法，或者没看懂其中某种解法，欢迎评论留言或者私聊 jsliang~

jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。