Top 100
Unique Binary Search Trees
- Problem
- LC 96
- File
- top100_LC96UniqueBinarySearchTrees.java
- Path
- pkg5leetcode/top100/top100_LC96UniqueBinarySearchTrees.java
- Package
- pkg5leetcode.top100
- Command
- java pkg5leetcode/top100/top100_LC96UniqueBinarySearchTrees.java
- Approach
- Catalan DP: ways(n) = sum ways(i)*ways(n-1-i).
- Complexity
- Time O(n^2), Space O(n)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.top100;2 3/*4 * Unique Binary Search Trees | LC 965 * APPROACH: Catalan DP: ways(n) = sum ways(i)*ways(n-1-i).6 * COMPLEXITY: Time O(n^2), Space O(n)7 */8public class top100_LC96UniqueBinarySearchTrees {9 static int numTrees(int n) {10 int[] dp = new int[n + 1];11 dp[0] = 1;12 for (int nodes = 1; nodes <= n; nodes++) {13 for (int root = 1; root <= nodes; root++)14 dp[nodes] += dp[root - 1] * dp[nodes - root];15 }16 return dp[n];17 }18 19 public static void main(String[] args) {20 check(numTrees(3) == 5, "case1");21 check(numTrees(1) == 1, "case2");22 System.out.println("all tests passed");23 }24 25 static void check(boolean cond, String name) {26 if (!cond) throw new AssertionError("FAILED: " + name);27 System.out.println(" PASS " + name);28 }29}