博客

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3

输出：5

示例 2：

输入：n = 1

输出：1

提示：

1 <= n <= 19


leetcode96 链接


思路，可以用动态规划的思路来做

class Solution:
    def numTrees(self, n: int) -> int:
        # g(n) = sum(f(i,n)),  f(i,n) 表示以 i 为 root 节点, 长度为 n 的二叉树的数量
        # f(i, n) = g(i-1) * g(n-i), 因为是 bst 树, 故 i 为 root 节点的左子树一共有 i-1 个节点，都小于 i，右子树同理
        if n <= 2:
            return n
        g = [0]*(n+1)
        g[0], g[1], g[2] = 1, 1, 2
        for i in range(3, n+1):
            curSum = 0
            for j in range(1, i+1):
                curSum += g[j-1]*g[i-j]
            g[i] = curSum
        return g[n]

leetcode 95 输出最后重建的二叉树，

leetcode 95 题目链接


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

示例 1：

输入：n = 3

输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

示例 2：

输入：n = 1

输出：[[1]]

提示：

1 <= n <= 8

# 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
import copy
class Solution:

    def genTrees(self, nums):
        if len(nums) == 0:
            return []
        elif len(nums) == 1:
            return [TreeNode(nums[0])]
        #print(nums)
        temp = []
        for i in range(len(nums)):
            root = TreeNode(nums[i])
            leftChild = self.genTrees(nums[:i])
            rightChild = self.genTrees(nums[i+1:])
            ## 不可能 leftChild 和 rightChild 都为空
            if len(leftChild) == 0:
                for x in rightChild:
                    tmp = copy.deepcopy(root)
                    tmp.right = x
                    temp.append(tmp)
            elif len(rightChild) == 0:
                for x in leftChild:
                    tmp = copy.deepcopy(root)
                    tmp.left = x
                    temp.append(tmp)
            else:
                for x in leftChild:
                    for y in rightChild:
                        tmp = copy.deepcopy(root)
                        tmp.left = x
                        tmp.right = y
                        temp.append(tmp)
        return temp

    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        if n == 1:
            return [TreeNode(1)]
        nums = [i for i in range(1, n+1)]
        return self.genTrees(nums)