95. 不同的二叉搜索树 II
题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/unique-binary-search-trees-ii
题目
给定一个整数 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
解题思路
思路：递归
这道题跟 96. 不同的二叉搜索树 有点类似。只是 96 题中，只需要求得可构建二叉搜索树的种数。而这道题当中，需要进行建树。
根据二叉搜索树的定义，在题目给定的区间 [1, n] 中，当我们枚举 i（i 属于 [1, n]） 作为根节点时，那么 [1, i-1] 将用以构建左子树，[i+1, n] 将用以构建右子树。
那么： 以 i 为根节点的可构建种类 = 左子树可构建种类 * 右子树可构建种类。
上述结论分析可参考：LeetCode 96. 不同的二叉搜索树 | Python
也就说，以 i 为根节点，从可构建的左子树集合当中选取一个，同时在可构建的右子树集合当中选取一个，与根节点 i 构建一个二叉树搜索树。
具体的代码实现如下。
代码实现
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
if n == 0:
return []
def get_all_bts(left, right):
if left > right:
return [None]
if left == right:
return [TreeNode(left)]
ans = []
for i in range(left, right+1):
# 开始进行枚举
# 左子树所有可能的情况
left_sub_trees = get_all_bts(left, i-1)
# 右子树所有可能的情况
right_sub_trees = get_all_bts(i+1, right)
# 从左子树跟右子树集合当中各取一种，与根节点构成二叉搜索树
for left_sub_tree in left_sub_trees:
for right_sub_tree in right_sub_trees:
root = TreeNode(i)
root.left = left_sub_tree
root.right = right_sub_tree
ans.append(root)
return ans
return get_all_bts(1, n)
实现结果
欢迎关注
公众号 【书所集录】
