95. 不同的二叉搜索树 II

https://leetcode-cn.com/problems/unique-binary-search-trees-ii/

解法一：递归

根据二叉搜索树的性质，在[1…n]中依次选择根i（1 <= i <= n），划分出左([1...i-1])右([i+1...n])子树，然后递归构造子树。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        if n == 0:  #边界情况
            return []
        res = self.genTrees(1, n)        
        return res

    #辅助函数，返回所有以[start...end]为根的树根节点
    def genTrees(self, start, end):
        List = []   #本层返回的结点列表
        if start > end:
            return [None]
        elif start == end:
            return [TreeNode(start)]
        else:
            for i in range(start, end+1):
                #以i为根，递归划分左右子树，得到所有可能的左右子树
                left = self.genTrees(start, i-1)
                right = self.genTrees(i+1, end)
                #以i为根，综合左右子树，构建所有情况的树，并将每种树的根节点写入列表
                for l in left:  #l，r的内外顺序可以反过来
                    for r in right:
                        root = TreeNode(i)
                        root.left = l
                        root.right = r
                        List.append(root)
        return List

js

/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function(n) {
  var genTrees = function(start, end) {
    const list  = []
    if (start > end) return [null]
    else if (start === end) return [new TreeNode(start)]
    else {
      for (let i = start; i <= end; i++) {
        let left = genTrees(start, i-1)
        let right = genTrees(i+1, end)
        for (let j = 0; j < left.length; j++) {
          for (let k = 0; k < right.length; k++) {
            let root = new TreeNode(i)
            root.left = left[j]
            root.right = right[k]
            list.push(root)
          }
        }
      }
    }
    return list
  }
  if (n === 0) return[]
  return genTrees(1, n)
};