二叉排序树求树个数
题目描述：给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。答案代码class Solution:
def numTrees(self, n: int) -> int:
stack = #f(0):一个空结点;f(1)
if n <= 1:
return stack
for m in range(2,n+1):#总共有n个结点
count = 0
for i in range(m): #第m个结点的二叉排序树的左右子树整数和是m-1
count += stack * stack
stack.append(count)
return stack
为什么 stack * stack左右子树的数量要相乘 为了计算由 n 个节点组成的不同二叉搜索树（BST）的数量，我们可以使用动态规划来解决。
设 \( G(n) \) 表示 n 个节点可以组成的二叉搜索树的总数。我们知道：
- \( G(0) = 1 \)（空树也是一种BST）
- \( G(1) = 1 \)（只有一个节点的树）
对于 \( n \geq 2 \)，我们可以这样理解：将每个节点从 1 到 n 作为根节点，剩下的节点构成左右子树。假设 \( i \) 是根节点：
- 左子树可以由节点 1 到 \( i-1 \) 组成，有 \( G(i-1) \) 种情况。
- 右子树可以由节点 \( i+1 \) 到 n 组成，有 \( G(n-i) \) 种情况。
因此，总的组合情况为：
\[ G(n) = \sum_{i=1}^{n} G(i-1) \times G(n-i) \]
下面的代码实现了这个逻辑：
class Solution:
def numTrees(self, n: int) -> int:
G = * (n + 1)
G, G = 1, 1
for i in range(2, n + 1):
for j in range(1, i + 1):
G += G * G
return G
这段代码使用数组 \( G \) 存储每个 \( G(n) \) 的计算结果，循环累加所有可能的左子树和右子树的组合。
希望这个解释和代码对你有所帮助！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]