95. 不同的二叉搜索樹 II

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

題目

給定一個整數(shù) n，生成所有由 1 ... n 為節(jié)點所組成的 二叉搜索樹 。

示例：

輸入：3
輸出：
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解釋：
以上的輸出對應(yīng)以下 5 種不同結(jié)構(gòu)的二叉搜索樹：

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

解題思路

思路：遞歸

這道題跟 96. 不同的二叉搜索樹 有點類似。只是 96 題中，只需要求得可構(gòu)建二叉搜索樹的種數(shù)。而這道題當(dāng)中，需要進(jìn)行建樹。

根據(jù)二叉搜索樹的定義，在題目給定的區(qū)間 [1, n] 中，當(dāng)我們枚舉 i（i 屬于 [1, n]） 作為根節(jié)點時，那么 [1, i-1] 將用以構(gòu)建左子樹，[i+1, n] 將用以構(gòu)建右子樹。

那么： 以 i 為根節(jié)點的可構(gòu)建種類 = 左子樹可構(gòu)建種類 * 右子樹可構(gòu)建種類。

上述結(jié)論分析可參考：LeetCode 96. 不同的二叉搜索樹 | Python

也就說，以 i 為根節(jié)點，從可構(gòu)建的左子樹集合當(dāng)中選取一個，同時在可構(gòu)建的右子樹集合當(dāng)中選取一個，與根節(jié)點 i 構(gòu)建一個二叉樹搜索樹。

具體的代碼實現(xiàn)如下。

代碼實現(xiàn)

# 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):
                # 開始進(jìn)行枚舉
                # 左子樹所有可能的情況
                left_sub_trees = get_all_bts(left, i-1)
                # 右子樹所有可能的情況
                right_sub_trees = get_all_bts(i+1, right)
                # 從左子樹跟右子樹集合當(dāng)中各取一種，與根節(jié)點構(gòu)成二叉搜索樹
                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)

實現(xiàn)結(jié)果

實現(xiàn)結(jié)果

歡迎關(guān)注

公眾號 【書所集錄】