Unique Binary Search Trees II | Leetcode

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

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

Confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

---

Solution: Iterate i from 1 to n, form new trees with node i as the root each time. In each recursion, always create a new list of trees. Then plug this list into the caller to get the answer.

When we try to generate an empty tree, it is important to set the tree as a null node, instead of not adding it as an answer. This is because this will simplify the logic when we set the left and right children of the parent node as null directly from the returned answer.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<TreeNode> generateTrees(int n) {
        return generateTrees(1, n);
    }
    
    private List<TreeNode> generateTrees(int first, int last) {
        List<TreeNode> answer = new ArrayList<>();
        if (first > last) {
            answer.add(null);
            return answer;
        }        
        for (int i = first; i <= last; i++) {
            List<TreeNode> leftTrees = generateTrees(first, i - 1);
            List<TreeNode> rightTrees = generateTrees(i + 1, last);
            
            for (TreeNode leftTree: leftTrees) {
                for (TreeNode rightTree: rightTrees) {
                    TreeNode root = new TreeNode(i);
                    root.left = leftTree;
                    root.right = rightTree;
                    answer.add(root);
                }
            }
        }
        return answer;
    }
}