Recursive Formula Solution - Unique Binary Search Trees

The idea is to find the formula which is to define an index equals to n - 1, loop by minus one each until reach middle, use 2 * recursive(index)*recursive(n - 1 - index)

if n is odd, n%2 == 1, then add one more recursive call recursive(n/2) * recursive(n/2)…

Another tricky is that set result = 1 if n == 0 … on purpose!  see the example of n = 3… 2 *recursive(2) *recursive(0)+ recursive(1)*recursive(1)...


public class Solution {
    public int numTrees(int n) {
        if(n == 0){
            return 1;
        }
   
        int index = n - 1;
        int result = 0;
        while(index >= (n+1)/2){
            result += (numTrees(index) * numTrees(n - index - 1)) * 2;
            index--;
        }
        if(n % 2 != 0){
            result+= numTrees(n / 2) * numTrees(n / 2);
        }
        return result;
    }
}