95. 不同的二叉搜索樹 II - 力扣（LeetCode）

# 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[Optional[TreeNode]]:if n == 0:return []return self._generate_trees(1, n)def _generate_trees(self, start, end):trees = []# 如果區間為空，則返回 [None] 作為空樹的情況if start > end:trees.append(None)return trees# 枚舉每個數字作為根節點for i in range(start, end + 1):# 遞歸生成所有可能的左子樹和右子樹left_trees = self._generate_trees(start, i - 1)right_trees = self._generate_trees(i + 1, end)# 將所有左子樹和右子樹組合起來for left in left_trees:for right in right_trees:root = TreeNode(i)root.left = leftroot.right = righttrees.append(root)return trees