- 标签：树、二叉搜索树、动态规划、回溯、二叉树
- 难度：中等
题目大意
#
给定一个整数 n，请返回以 1 到 n 为节点构成的「二叉搜索树」，可以按任意顺序返回答案。
解题思路
#
如果根节点为 i，则左子树的节点为 (1, 2, ..., i - 1)，右子树的节点为 (i + 1, i + 2, ..., n)。可以递归的构建二叉树。
定义递归函数 generateTrees(start, end)，表示生成 [left, ..., right] 构成的所有可能的二叉搜索树。
- 如果
start > end，返回 [None]。
- 初始化存放所有可能二叉搜索树的数组。
- 遍历
[left, ..., right] 的每一个节点 i，将其作为根节点。
- 递归构建左右子树。
- 将所有符合要求的左右子树组合起来，将其加入到存放二叉搜索树的数组中。
- 返回存放二叉搜索树的数组。
代码
#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
if n == 0:
return []
def generateTrees(start, end):
if start > end:
return [None]
trees = []
for i in range(start, end+1):
left_trees = generateTrees(start, i - 1)
right_trees = generateTrees(i + 1, end)
for left_tree in left_trees:
for right_tree in right_trees:
curr_tree = TreeNode(i)
curr_tree.left = left_tree
curr_tree.right = right_tree
trees.append(curr_tree)
return trees
return generateTrees(1, n)
|