/ Data Structure and Algorithms  

Leetcode 95. Unique Binary Search Trees II

Question



Given n, use these numbers 1 ... n to generate all possible binary search trees.

Similar Questions

Solution

One of the most important property of binary tree: all values of the left subtree are smaller than the root node, and all values of the right subtree are larger than the root node. We could use it to solve this problem

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.

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
public List<TreeNode> generateTrees(int n) {
    if (n == 0) {
        return Collections.emptyList();
    }

    return getResults(1, n);
}

// recursive
private static List<TreeNode> getResults(int start, int end) {
    List<TreeNode> results = new ArrayList<>();

    if (start > end) {
        results.add(null);

        return results;
    }

    // only 1 node
    if (start == end) {
        TreeNode node = new TreeNode(start);
        results.add(node);

        return results;
    }

    for (int i = start; i <= end; i++) {
        // i is the root node
        List<TreeNode> leftNodes = getResults(start, i - 1);
        List<TreeNode> rightNodes = getResults(i + 1, end);

        // combine all possible left and right tree
        for (TreeNode leftNode : leftNodes) {
            for (TreeNode rightNode : rightNodes) {
                TreeNode root = new TreeNode(i);

                root.left = leftNode;
                root.right = rightNode;

                results.add(root);
            }
        }
    }

    return results;
}