95. Unique Binary Search Trees II

recursion or dp

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        // start->end
        return recursion(1,n);
    }
    
    private List<TreeNode> recursion(int start, int end){
        List<TreeNode> list = new LinkedList<>();
        if (start>end){
            list.add(null);
            return list;
        }
        
        for(int i=start; i<=end; i++){
            List<TreeNode> leftList= recursion(start, i-1);
            List<TreeNode> rightList = recursion(i+1, end);
            for(TreeNode leftNode: leftList){
                for(TreeNode rightNode: rightList){
                    TreeNode node=new TreeNode(i);
                    node.left = leftNode;
                    node.right = rightNode;
                    list.add(node);
                }
            }
        }
        return list;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode>[] ans = new List[n+1];
        ans[0]=new LinkedList<>();
        ans[0].add(null);
        ans[1]=new LinkedList<>();
        ans[1].add(new TreeNode(1));
        
        for(int i=2; i<=n; i++){
            ans[i]= new LinkedList<>();
            // node(j) is the root
            for(int j=1; j<=i; j++){
                List<TreeNode> left = ans[j-1];
                // right mirrors the left part
                // 1. number of right nodes = i-j;
                // 2. the value of right node = original left node val + rootNode val
                List<TreeNode> right = ans[i-j];
                for(TreeNode nodeL: left){
                    for(TreeNode nodeR: right){
                        TreeNode node = new TreeNode(j);
                        node.left = nodeL;
                        node.right = generateRightCopy(nodeR, j);
                        ans[i].add(node);
                    }
                } 
            }
        }
        return ans[n];
    }
    
    private TreeNode generateRightCopy(TreeNode node, int offset){
        if (node==null) return null;
        TreeNode newNode = new TreeNode(node.val+offset);
        newNode.left = generateRightCopy(node.left, offset);
        newNode.right = generateRightCopy(node.right, offset);
        return newNode;
    }
}