95. 不同的二叉搜索树 II

题目

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

难度：🌟🌟🌟🌟

示例 1：

输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

• 1 <= n <= 8

题解

想要构造出所有合法的 BST，分三步：

1. 穷举 root 节点的所有可能；
2. 递归构造出左右子树的所有合法 BST；
3. 给 root 节点穷举所有左右子树的组合。

代码实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func generateTrees(n int) []*TreeNode {
	if n == 0 {
		return nil
	}
	return build(1, n)
}

func build(lo, hi int) (res []*TreeNode) {
	if lo > hi {
		res = append(res, nil)
		return
	}
	for i := lo; i <= hi; i++ {
		leftTree := build(lo, i-1)
		rightTree := build(i+1, hi)
		// 固定左孩子，遍历右孩子
		for _, left := range leftTree {
			for _, right := range rightTree {
				root := &TreeNode{Val: i}
				root.Left = left
				root.Right = right
				res = append(res, root)
			}
		}
	}
	return
}