96. Unique Binary Search Trees (Medium)
https://leetcode.com/problems/unique-binary-search-trees/
Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?
Example:
Input: 3 Output: 5 Explanation: 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
Solutions
class Solution {
// key is the quantity of nodes, value is the possible situations of unique BSTs.
private Map<Integer, Integer> situations = new HashMap<>();
public int numTrees(int n) {
// for n nodes, possible situations:
// 1. left 0 nodes, right n-1 nodes
// 2. left 1 nodes, right n-2 nodes
// ...
// i+1. left i nodes, right n-i-1 nodes
// ...
// n. left n-1 nodes, right 0 nodes
if (n <= 1) {
return 1;
}
if (n == 2) {
return 2;
}
if (situations.containsKey(n)) {
return situations.get(n);
}
int ans = 0;
for (int i = 0; i < n; i++) {
int left = numTrees(i);
int right = numTrees(n - i - 1);
ans += left * right;
}
situations.put(n, ans);
return ans;
}
}