leetcode-95

95. 不同的二叉搜索树 II

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

输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

官方题解回溯

二叉搜索树关键的性质是根节点的值大于左子树所有节点的值，小于右子树所有节点的值，且左子树和右子树也同样为二叉搜索树。

在生成所有可行的二叉搜索树时，假设当前序列长度为$n$，如果枚举根结点的值为$i$，则根据二叉搜索树的性质可知左子树的节点值的集合为$[1,\dots,i-1]$，右子树的节点值的集合为$[i+1,\dots,n]$。而左子树和右子树的生成相较于原问题是一个序列长度缩小的子问题，因此可以想到用回溯的方法来解决这道题目。

定义generateTrees(start, end)函数表示当前值的集合为$[start, end]$，返回序列$[start, end]$生成的所有可行的二叉搜索树。按前面的思路，考虑枚举$[start,end]$中的值 $i$ 为当前二叉搜索树的根，则序列划分为 $[start, i-1]$和$[i+1, end]$两部分。

通过递归调用这两部分，既generateTrees(start, i-1)和 generateTrees(i+1, end)，获得所有可行的左子树和可行的右子树，最后我们只需从可行左子树集合中选一颗，再从右子树集合中选一颗拼接到根节点上，并将生成的二叉搜索树放入答案数组即可。

递归的入口即为generateTrees(1, n)，出口为当 start>end的时候，当前二叉搜索树为空，返回空节点。

class Solution:
    def generateTrees(self, n: int):
        def generateTrees(start, end):
            if start > end:
                return [None,]
            
            allTrees = []
            #枚举可行根节点
            for i in range(start,end+1): 

                # 获得所有可行的左子树集合
                leftTrees = generateTrees(start,i-1)

                # 获得所有可行的右子树集合
                rightTrees = generateTrees(i+1,end)

                # 从左子树集合选出左子树，从右子树集合选出右子树，拼接到根节点
                for l in leftTrees:
                    for r in rightTrees:
                        curTree = TreeNode(i)
                        curTree.left = l
                        curTree.right = r
                        allTrees.append(curTree)
            return allTrees
        
        return generateTrees(1,n) if n else []