二叉排序树求树个数

Terence888

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

答案代码

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

为什么

 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) \]

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

class Solution:
    def numTrees(self, n: int) -> int:
        G = [0] * (n + 1)
        G[0], G[1] = 1, 1

        for i in range(2, n + 1):
            for j in range(1, i + 1):
                G[i] += G[j - 1] * G[i - j]

        return G[n]

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

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

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