[数据结构与算法]95. 不同的二叉搜索树 II

95. 不同的二叉搜索树 II

原始题目链接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii/

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

解题思路：

回溯法，定义一个函数：G(s, e)函数表示当前值的集合为[start,end]，返回序列[start,end]生成的所有可行的二叉搜索树，枚举 [start,end] 中的值 i
为当前二叉搜索树的根，序列就被i分成了左右2部分（start，i-1）（i+1，end），然后递归调用这两部分，获得以i为根的左右两个子二叉树搜索树的结果集合，再从左右两个结果集合中分别抽出一个结果进行拼接，形成当前i为根的所有二叉搜索树的结果。具体实现看代码及注释。

代码实现：

# 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[TreeNode]:
        # 定义一个函数：G(s, e)
        # 函数表示当前值的集合为[start,end]，返回序列[start,end] 生成的所有可行的二叉搜索树
        def G(s, e):
            # 如果s 大于 e，不满足二叉搜索树的条件，返回空树
            if s > e:
                return [None, ]
            res = []

            # 遍历s到e的每一个节点，作为根节点
            for i in range(s, e + 1):

                # 递归调用左子树，获取结果
                left = G(s, i - 1)
                # 递归调用右子树，获取结果
                right = G(i + 1, e)

                # 从左右子树的结果中，各找出一棵树和当前节点i进行拼接，组成一个结果
                for l in left:
                    for r in right:
                        t = TreeNode(i)
                        t.left = l
                        t.right = r
                        res.append(t)
            return res

        return G(1, n) if n else []

参考文献：
https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/bu-tong-de-er-cha-sou-suo-shu-ii-by-leetcode-solut/