昆山兼职做网站,一家专门做房产特卖的网站,微信小程序游戏制作,电商个人网站建设给你一个整数 n #xff0c;求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种#xff1f;返回满足题意的二叉搜索树的种数。
示例 1#xff1a; 输入#xff1a;n 3 输出#xff1a;5
示例 2#xff1a; 输入#xff1a;n 1 输出#xff1a;1…给你一个整数 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]*(n1)g[0], g[1], g[2] 1, 1, 2for i in range(3, n1):curSum 0for j in range(1, i1):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, val0, leftNone, rightNone):
# 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[i1:])## 不可能 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, n1)]return self.genTrees(nums)
