当前位置：首页 > news >正文

leetcode 96 不同的二叉搜索树

news 2025/7/16 3:43:43

给你一个整数 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 ng = [0]*(n+1)g[0], g[1], g[2] = 1, 1, 2for i in range(3, n+1):curSum = 0for j in range(1, i+1):curSum += g[j-1]*g[i-j]g[i] = curSumreturn 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 = xtemp.append(tmp)elif len(rightChild) == 0:for x in leftChild:tmp = copy.deepcopy(root)tmp.left = xtemp.append(tmp)else:for x in leftChild:for y in rightChild:tmp = copy.deepcopy(root)tmp.left = xtmp.right = ytemp.append(tmp)return tempdef 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)