96. Unique Binary Search Trees

小鱼儿 2022-03-07 01:14 254阅读 0赞

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

Example:

  1. Input: 3
  2. Output: 5
  3. Explanation:
  4. Given n = 3, there are a total of 5 unique BST's:
  6.    1         3     3      2      1
  7.     \       /     /      / \      \
  8.      3     2     1      1   3      2
  9.     /     /       \                 \
  10.    2     1         2                 3

难度：medium

题目：给定整数n，计算有多少种BST结构。

  1. class Solution {
  2.     public int numTrees(int n) {
  3.         long c = 1;
  4.         // Catalan number
  5.         // Catalan (n+1) = (4n+2) / (n+2) Catalan n
  6.         for(int i = 1; i < n; i++){
  7.             c = c * 2 * (2 * i + 1) / (i + 2);
  8.         }
  10.         return (int) c;
  11.     }
  12. }

发表评论

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

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

相关阅读