🌵95. Unique Binary Search Trees II
https://leetcode.com/problems/unique-binary-search-trees-ii/
参考：
js
/**
* 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 []
}
return genSubTrees(1, n)
};
function genSubTrees(min, max) {
const trees = []
if (min > max) {
trees.push(null)
return trees
}
for (let i = min; i <= max; i++) {
const leftTrees = genSubTree(min, i - 1)
const rightTrees = genSubTree(i + 1, max)
leftTrees.forEach(left => {
rightTrees.forEach(right => {
const root = new TreeNode(i)
root.left = left
root.right = right
trees.push(root)
})
})
}
return trees
}py
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n <= 0:
return []
return self.genSubTrees(1, n)
def genSubTrees(self, minVal, maxVal):
trees = []
if minVal > maxVal:
trees.append(None)
return trees
for i in range(minVal, maxVal + 1):
leftTrees = self.genSubTrees(minVal, i - 1)
rightTrees = self.genSubTrees(i + 1, maxVal)
for left in leftTrees:
for right in rightTrees:
root = TreeNode(i)
root.left = left
root.right = right
trees.append(root)
return treesgo
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func generateTrees(n int) []*TreeNode {
if n <= 0 {
return []*TreeNode{}
}
return genSubTrees(1, n)
}
func genSubTrees(min, max int) []*TreeNode {
trees := []*TreeNode{}
if min > max {
trees = append(trees, nil)
return trees
}
for i := min; i <= max; i++ {
leftTrees := genSubTrees(min, i-1)
rightTrees := genSubTrees(i+1, max)
for _, left := range leftTrees {
for _, right := range rightTrees {
root := &TreeNode{
Val: i,
Left: left,
Right: right,
}
trees = append(trees, root)
}
}
}
return trees
}