1. 不同的二叉搜索树 II
给定一个整数 n ，请生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。
class Solution:
def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
if n == 0:
return []
return self.generateTreesHelper(1, n)
def generateTreesHelper(self, start, end):
if start > end:
return [None]
all_trees = []
for i in range(start, end + 1):
left_trees = self.generateTreesHelper(start, i - 1)
right_trees = self.generateTreesHelper(i + 1, end)
for l in left_trees:
for r in right_trees:
current_tree = TreeNode(i)
current_tree.left = l
current_tree.right = r
all_trees.append(current_tree)
return all_trees
2. 不同的二叉搜索树
给定一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？
class Solution:
def numTrees(self, n: int) -> int:
dp = [0] * (n + 1)
dp[0] = dp[1] = 1
for i in range(2, n + 1):
for j in range(1, i + 1):
dp[i] += dp[j - 1] * dp[i - j]
return dp[n]