95. Unique Binary Search Trees II

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

参考：

• http://bangbingsyb.blogspot.com/2014/11/leetcode-unique-binary-search-trees-i-ii.html

JavaScript

/**
 * 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
}

Python

# 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 trees

Go

/**
 * 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
}