LeetCode 不同的二叉搜索树II题解
题目描述
给定一个整数 n，生成所有由 1...n 为节点所组成的二叉搜索树。
示例：
输入：n = 3
输出：[[1,null,3,null,2],[3,2,null,1,null,3,null,2],[3,1,null,null,2],[2,1,3],[1,null,2,null,3]]
解题思路
方法：分治
思路：
- 使用分治思想生成所有二叉搜索树。
- 对于每个根节点，递归生成左子树和右子树。
- 组合所有可能的左子树和右子树。
复杂度分析：
- 时间复杂度：O(Catalan(n))。
- 空间复杂度：O(n)。
代码实现
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def generate_trees(n): def helper(start, end): if start > end: return [None] all_trees = [] for i in range(start, end + 1): left_trees = helper(start, i - 1) right_trees = helper(i + 1, end) for left in left_trees: for right in right_trees: root = TreeNode(i) root.left = left root.right = right all_trees.append(root) return all_trees return helper(1, n) if n else [] # 测试 def test_generate_trees(): n = 3 trees = generate_trees(n) print(len(trees)) # 输出：5 if __name__ == "__main__": test_generate_trees()总结
不同的二叉搜索树II是分治思想的典型应用，递归生成所有可能的二叉搜索树。
