leetcode 96. Unique Binary Search Trees

Coding_Reading

于 2017-06-04 23:04:36 发布

阅读量287

点赞数

分类专栏： LeetCode 二叉树文章标签： leetcode

本文链接：https://blog.csdn.net/ProgrammeringLearner/article/details/72862434

版权

LeetCode 同时被 2 个专栏收录

32 篇文章

订阅专栏

二叉树

3 篇文章

订阅专栏

本文介绍了一种计算不同形态二叉搜索树数量的方法。通过递归思想建立数学模型，利用动态规划求解，适用于算法竞赛及面试题目。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目：
这里写图片描述

思路：
以k为根节点的树，左子树为【1，…，K - 1】，右子树为【K + 1，…，N】，定义f(n)为【1，…，n】能产生不同的二叉搜索树的个数，则以K为根节点能产生f(k - 1) * f(n - k)种不同的树。

显然f(0) = f(1) = 1。
f(2) = f(0) * f(1) + f(1) * f(0)
f(3) = f(0) * f(2) + f(1) * f(1) + f(2) * f(0) //分别以1,2,3为根

由此可以推出递推式 $f(n) = \sum_{k = 1}^nf(k - 1)*f(n - k)$

AC解：

class Solution {
public:
    int numTrees(int n) 
    {
        vector<int> f(n + 1, 0);
        f[0] = f[1] = 1;
        for (int i = 2; i <= n; i++)
            for (int k = 1; k <= i; k++)
                f[i] += f[k - 1] * f[i - k];

        return f[n];
    }
};