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;
    }
}

Incorrect Solutions

References