Open rushcheyo opened 8 years ago
N 个节点的 BST 的形态为 Catalan 数的第 N 项,即 C(2n, n) / (n + 1) => (2n)! / n! / (n + 1),最后可以写成这样:
class Solution { public: int numTrees(int n) { long ans = 1; for (int i = 1; i <= n; ++i) ans += ans * n / i; return ans / (n + 1); } };
N 个节点的 BST 的形态为 Catalan 数的第 N 项,即 C(2n, n) / (n + 1) => (2n)! / n! / (n + 1),最后可以写成这样: