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.
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 3Solution:O(n)
public class Solution {
public int numTrees(int n) {
if(n==0)
return 1;
if(n == 1)
return 1;
if(n == 2)
return 2;
int ret = 0;
for(int k = 1; k<=n ;k++)
ret+= (numTrees(k-1)* numTrees(n-k));
return ret;
}
}
沒有留言:
張貼留言