Unique Binary Search Trees II

LeetCode Q 95 - Unique Binary Search Trees II

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

Example:
Input: 3 Output: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ]

Solution : DP

Code:

public List<TreeNode> generateTrees(int n) {
	if (n == 0) return new ArrayList<>();
	return generate(1, n);
}

private List<TreeNode> generate (int start, int end) {
	List<TreeNode> res = new ArrayList<>();
	if (start > end) {
		res.add(null); return;
	}

	if (start == end) {
		res.add(new TreeNode(start)); return;
	}


	for (int i = start; i <= end; i++) {
		List<TreeNode> leftNodes = generate(start, i - 1);
		List<TreeNode> rightNodes = generate(i + 1, end);
	
	for (TreeNode l: leftNodes) {
		for (TreeNode r: rightNodes) {
			TreeNode root = new TreeNode(i);
			root.left = l; root.right = r;
			res.add(root);
		}
	}

	return res;
}