/ Data Structure and Algorithms  

Leetcode 96. Unique Binary Search Trees

Question



Similar to 95. Unique Binary Search Trees II. This time just need to count the number of unique binary search tree.

Similar Questions

Solution

The following is the analysis for 95. Unique Binary Search Trees II:

Example: 1....n
Take 1 as the root node, [] as the left subtree, and all of [2 ... n] as the right subtree.
Take 2 as the root node, [1] as the left subtree, [3 ... n] as the right subtree.
Take 3 as the root node, [1 2] as the left subtree, [4 ... n] as the right subtree. Then pair the left and right subtrees.
Take 4 as the root node, [1 2 3] as the left subtree, [5 ... n] as the right subtree. Then pair the left and right subtrees.
…
Take n as the root node, [1 ... n] as the left subtree, [] as the right subtree.
If there is only one number, then there is only 1 case, using that number as a tree. If it is [], it returns null.

For this problem, it will be simpler, we only need to return the number of trees. To find the number of subtrees of current roots, just multiply the number of left subtrees by the right subtree.

As there are many repeated calculations, we can save the results obtained during the recursion, and it can be taken directly when needed for the second time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// dynamic programming values, map n -> number of valid trees
Map<Integer, Integer> map = new HashMap<>();

public int numTrees(int n) {
    // initialize values
    map.put(0, 1);
    map.put(1, 1);
    map.put(2, 2);

    return getAnswer(n);
}

private int getAnswer(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }

    if (n == 2) {
        return 2;
    }

    int result = 0;

    for (int i = 1; i <= n; i++) {
        // root element is i, 
        // number of left node = i - i
        // number of right node = n - i
        int left;
        if (map.containsKey(i - 1)) {
            left = map.get(i - 1);
        } else {
            left = getAnswer(i - 1);
            map.put(i - 1, left);
        }

        int right;
        if (map.containsKey(n - i)) {
            right = map.get(n - i);
        } else {
            right = getAnswer(n - i);
            map.put(n - i, right);
        }

        result += left * right;
    }

    map.put(n, result);
    return result;
}