LeetCode96——Unique Binary Search Trees

た 入场券 2022-08-21 00:04 138阅读 0赞

LeetCode96——Unique Binary Search Trees

结构不同的二叉树个数，比起上一题，因为只要求出个数，我们只需要利用卡特兰数的递推式子构造动归方程就很容易解决。

原题

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example,
Given n = 3, there are a total of 5 unique BST’s.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

这里说BST，是查找二叉树，这对构造这些数就有一定要求，当然这是上一题讨论的问题，这里只需要求个数就OK。直接卡特兰数解决

代码

递归公式：
C0=1,Cn+1=2(2n+1)n+2⋅Cn

  1. class Solution {
  2. public:
  3.     int numTrees(int n) {
  4.         vector<long>C(n+1);
  5.         C[0] = 1;
  6.         for (int i = 0; i < n; i++)
  7.         {
  8.             C[i + 1] = (2 * (2 * i + 1)*C[i]) / (i + 2);
  9.         }
  10.         return C[n];
  11.     }
  12. };

注意就是卡特兰数数列到后面变得非常大，超过了int的范围，我们用long来保存临时结果。

发表评论

表情：
评论列表 （有 0 条评论，138人围观）

还没有评论，来说两句吧...

相关阅读