LeetCode link

first thought

  • Selected 1…n as the root
  • For each selection, the count is the multiplication of the count of it’s left sub tree and the right(DFS).
  • The total sum of n is the sum of each selection.
  • Using a array to cache the count of n.

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
class Solution {
    public int numTrees(int n) {
        if (n == 1) {
            return 1;
        }
        int[] count = new int[n];
        return this.numTrees(n, count);
    }
    private int numTrees(int n, int[] count) {
        if (n == 1 || n == 0) {
            return 1;
        }
        if (count[n - 1] > 0) {
            return count[n - 1];
        }
        int number = 0;
        for (int i = 1; i <= n; i++) {
            number += (this.numTrees(i - 1, count) * this.numTrees(n - i, count));
        }
        count[n - 1] = number;
        return number;
    }
}