[LeetCode] 95. Unique Binary Search Trees II

Posted on | In

Problem

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input: 3
Output:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Explanation

  1. We can use recusion method to solve this problem. When the input is n, we can have from 1 to n as the root node. From the above example when input is 3, we can have 1 as the root node, 2 as the root node, and 3 as the root node. Then, we need to find the sum of unique BST when every element as the root node. So when 1 as the root node, there are 2 unique BST; when 2 as the root node, there is 1 unique BST; when 3 as the root node, there are 2 unique BST. So when input is 3, there are 5 unique BST.

  2. When input is $n$, we can choose from 1 to n as the root node. If $1 \leq k \leq n$, and we want to find how many unique BST when $k$ is the root node. So, on its left side, the nodes can only be from 1 to k-1, on its right side, the nodes can only be from k+1 to n. We can see that the constrution of unqiue BST on its left side and right side is the same as the construction from 1 to n. So we should use the same recursion method to find the unique BST on left and right. After we find the BST of left side and right side, then we connect them to the root node $k$. Therefore, the steps are first iterate every element as the root node; second calling the helper function of its left to create a list of unique BST and calling the helper function of its right to create a list of BST. Third, connect root node k with every unique BST in the left list with every unique BST in the right list.

  3. The base case in the range, the min is greater than max, then we return the empty list. For example, when the range is from 1 to k, so min = 1, max = k, if the current root we choose is k, we need to find its left side from 1 to k-1, and right side from k+1 to k, which is invalid and we return the empty list.

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
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
50
51
52
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<TreeNode> helper(int min, int max) {
        List<TreeNode> res = new ArrayList<>();
        if (min > max) return res;
        for (int rt = min; rt <= max; rt++) {
            List<TreeNode> left = helper(min, rt-1);
            List<TreeNode> right = helper(rt+1, max);

            if (left.size() == 0 && right.size() == 0) {
                TreeNode root = new TreeNode(rt);
                res.add(root);
                return res;
            } else if (left.size() == 0) {
                for (TreeNode ri : right) {
                    TreeNode root = new TreeNode(rt);
                    root.right = ri;
                    res.add(root);
                }
            } else if (right.size() == 0) {
                for (TreeNode le : left) {
                    TreeNode root = new TreeNode(rt);
                    root.left = le;
                    res.add(root);
                }
            } else {
                for (TreeNode le : left) {
                    for (TreeNode ri : right) {
                        TreeNode root = new TreeNode(rt);
                        root.left = le;
                        root.right = ri;
                        res.add(root);
                    }
                }
            }
        }

        return res;
    }

    public List<TreeNode> generateTrees(int n) {
        return helper(1, n);
    }
}