Title: Unique Binary Search Trees Source: leetcode.com
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 2 3 4 5 |
1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 |
Java solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
/* https://leetcode.com/problems/unique-binary-search-trees/ */ class UniqueBinarySearchTrees { public static void main(String args[]) { UniqueBinarySearchTrees solution = new UniqueBinarySearchTrees(); System.out.println(solution.numTrees(4)); } public int numTrees(int n) { if(n<=0) return 1; int dp[] = new int[n+1]; dp[0] = 1; for(int i=1;i<=n;i++) { dp[n] = dp[n] + helper(dp, i-1) * helper(dp, n-i); } return dp[n]; } int helper(int[] dp, int n) { if(dp[n]!=0) return dp[n]; else { for(int i=1;i<=n;i++) dp[n] = dp[n] + helper(dp, i-1) * helper(dp, n-i); } return dp[n]; } } |