LeetCode 95. 不同的二叉搜索树 II | Python

95. 不同的二叉搜索树 II

题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/unique-binary-search-trees-ii

题目

给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。

示例：

输入：3
输出：
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释：
以上的输出对应以下 5 种不同结构的二叉搜索树：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

解题思路

思路：递归

这道题跟 96. 不同的二叉搜索树有点类似。只是 96 题中，只需要求得可构建二叉搜索树的种数。而这道题当中，需要进行建树。

根据二叉搜索树的定义，在题目给定的区间 [1, n] 中，当我们枚举 i（i 属于 [1, n]）作为根节点时，那么 [1, i-1] 将用以构建左子树，[i+1, n] 将用以构建右子树。

那么： 以 i 为根节点的可构建种类 = 左子树可构建种类 * 右子树可构建种类。

上述结论分析可参考：LeetCode 96. 不同的二叉搜索树 | Python

也就说，以 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]:
        if n == 0:
            return []
        
        def get_all_bts(left, right):
            if left > right:
                return [None]
            if left == right:
                return [TreeNode(left)]

            ans = []
            for i in range(left, right+1):
                # 开始进行枚举
                # 左子树所有可能的情况
                left_sub_trees = get_all_bts(left, i-1)
                # 右子树所有可能的情况
                right_sub_trees = get_all_bts(i+1, right)
                # 从左子树跟右子树集合当中各取一种，与根节点构成二叉搜索树
                for left_sub_tree in left_sub_trees:
                    for right_sub_tree in right_sub_trees:
                        root = TreeNode(i)
                        root.left = left_sub_tree
                        root.right = right_sub_tree
                        ans.append(root)
            return ans
        return get_all_bts(1, n)

实现结果

欢迎关注

公众号【书所集录】