96. Unique Binary Search Trees

xiaoxiao2021-02-28  12

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

给定一个序列1~n,为了构造二叉树,我们可以使用1~n中的第 i 个节点作为根节点,则根据二叉排序树的性质,1~n-1必在左子树,n+1~n在右子树;

f(0)= 1; f(1) = 1; f(2) = f(1) * f(0) + f(0) * f(1); 以第 i 个节点作为根节点有f(i - 1) * f( n - 1 - i)中二叉排序树的可能; 则f(n) = f(0) * f(n - 1) + f(1) * f(n-2)+…+f(n-1) * f(0)

思路1:用一个二重循环

int numTrees(int n) { if (n == 0)return 0; if (n == 1)return 1; vector<int> res(n + 1, 0); res[0] = 1, res[1] = 1; for (int i = 2; i <= n; i++){ for (int j = 1; j <= i; j++){ res[i] += res[j - 1] * res[i - j]; } } return res[n]; }

思路2:递归

int numTrees(int n) { if (n == 0 || n == 1)return 1; int res = 0; for (int i = 0; i < n; i++){ res += numTrees(i) * numTrees(n - i - 1); } return res; }

思路3:数学公式直接求解

int numTrees(int n) { if (n == 0)return 0; if (n == 1)return 1; vector<long>res(n + 1, 0); res[0] = 1, res[1] = 1; for (int i = 1; i < n; i++){ res[i + 1] = 2 * (2 * i + 1) *res[i] / (i + 2); } return res[n]; }
转载请注明原文地址: https://www.6miu.com/read-200355.html

最新回复(0)