二叉排序树求树个数

Terence888

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

答案代码

1. class Solution:
   
2.     def numTrees(self, n: int) -> int:
   
3.         stack = [1,1] #f(0):一个空结点;f(1)
   
4.         if n <= 1:
   
5.             return stack[n]
   
6.         for m in range(2,n+1):#总共有n个结点
   
7.             count = 0
   
8.             for i in range(m): #第m个结点的二叉排序树的左右子树整数和是m-1
   
9.                 count += stack[i] * stack[m-1-i]
   
10.             stack.append(count)
    
11.         return stack[n]

复制代码

为什么

1. stack[i] * stack[m-1-i]

复制代码

左右子树的数量要相乘

FishC

为了计算由 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) \]

下面的代码实现了这个逻辑：

1. class Solution:
   
2.     def numTrees(self, n: int) -> int:
   
3.         G = [0] * (n + 1)
   
4.         G[0], G[1] = 1, 1
   
5. 
   
6.         for i in range(2, n + 1):
   
7.             for j in range(1, i + 1):
   
8.                 G[i] += G[j - 1] * G[i - j]
   
9. 
   
10.         return G[n]

复制代码

这段代码使用数组 \( G \) 存储每个 \( G(n) \) 的计算结果，循环累加所有可能的左子树和右子树的组合。

希望这个解释和代码对你有所帮助！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。