20200716-95.unique-binary-search-trees-ii.md

#95.unique-binary-search-trees-ii

题目链接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii/

参考链接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/bu-tong-de-er-cha-sou-suo-shu-ii-by-leetcode/

题目

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

提示:

0 <= n <= 8

解题

思路[1]递归

• 先确定一个节点为根节点，因为是二叉搜索树，所以它的左节点列表和右列表是固定的，然后左右两两结合，就是以该节点为根节点的二叉搜索树的个数
• 递归的终点，节点列表的start > end，意味着上层节点的根节点的左列表或者右列表是空的，即他的子节点为null
• 递归的过程
  • 选中根节点。找到左列表，右列表
  • 根据左列表和右列表找到左节点列表和右节点列表
  • 结合两个列表，生成该根节点的节点列表，并返回

代码

/**
 * 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) {
  let helper = (start, end) => {
    let arr = []
    if(start > end){
      return [void 0];
    }
    for(let i = start; i <= end; i++){
      let left = helper(start, i-1);
      let right = helper(i+1, end);
      for(let j = 0; j < left.length; j++){
        for(let k = 0; k < right.length; k++){
          let node = new TreeNode(i, left[j], right[k])
          arr.push(node)
        }
      }
    }
    return arr
  }
  if(n === 0 ){
    return []
  }
  return helper(1, n)
};

思考