Unique Binary Search Trees II

Description

https://leetcode.com/problems/unique-binary-search-trees-ii/description/

Code

Inspired by Unique Binary Search Trees, we use the divide and conquer strategy to solve the count of the different binary tree. In this quesiton, we can also apply this to the generation of trees.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> ret = new LinkedList<TreeNode>();
        if (n <= 0) {
            return ret;
        }
        return generatePartial(1, n);
    }
        
        
    public List<TreeNode> generatePartial(int start, int end) {
        
        List<TreeNode> ret = new LinkedList<TreeNode>();
        if (start > end) {
            ret.add(null);
            return ret;
        }
        for (int i = start; i <= end; i++){
            List<TreeNode> left_list = generatePartial(start, i - 1);
            List<TreeNode> right_list = generatePartial(i + 1, end);
            
            for(TreeNode left_root : left_list) {
                for (TreeNode right_root: right_list) {
                    TreeNode root = new TreeNode(i);
                    root.left = left_root;
                    root.right = right_root;   
                    ret.add(root);
                }
            }
        }
        return ret;
    } 
}