LeetCode 96.不同的二叉搜索树
题目
给定一个整数 n,求以 1 … n 为节点组成的二叉搜索树有多少种?
示例:1
2
3
4
5
6
7
8
9
10输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
思路 + 代码
动态规划。
假设 整数 n对应的二叉搜索树数量为 G(n)。
每个节点 i ∈ (0,n] 为根节点对应的二叉搜索树数量为 F(i)。
则, G(n) = F(1) + F(2) + F(3) + … + F(n)。
而 节点i 为根节点的二叉搜索树,可以分为 i-1 个左子树 跟 n-i个右子树,F(i) = G(i-1)*G(n-i);
因此 G(n) = G(0)G(n-1) + G(1)G(n-2) + G(2)G(n-3) + … + G(n-1)G(0)
因此
1 | class Solution { |
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/unique-binary-search-trees
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 孙云增的博客!
评论