95. 不同的二叉搜索树 II

题目描述

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

思路

二叉搜索树的性质是：

性质

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉搜索树；

指向原始笔记的链接

假设一共 n 个节点，我们选择第 i 个节点为根节点，那么左边的节点一定是 [0, i-1]，右边的节点则是 [i+1, n]，这样我们可以将这个问题分解成子问题。

我们可以定义一个函数 genTrees(start, end)，表示生成从 start 到 end 的所有树，每次 genTrees 时，遍历 [start, end]，获取所有可能的左子树和右子树，再从中选取左右子树分别构建。

假设我们要开始建立树，则第一次调用的是 genTree(1, n)。在这个函数中遍历 [1, n]，假设根节点为 i，则递归地去生成 leftTree=[start, i-1]，rightTree=[i+1,end] 的 Tree。

那终止条件是什么？如果 start==end，那么返回当前节点，也可以使用 genTree() 实现，因此终止条件是 start>end。

如果 n 为 0，返回空列表。

最终代码：

class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        def genTree(start, end):
            if start > end:
                return [None, ]
            allTrees = []
            for i in range(start, end+1):
                leftTrees = genTree(start, i-1)
                rightTrees = genTree(i+1, end)
                for l in leftTrees:
                    for r in rightTrees:
                        currTree = TreeNode(i)
                        currTree.left = l
                        currTree.right = r
                        allTrees.append(currTree)
            return allTrees
        return genTree(1, n) if n else []

想得太多