Unique Binary Search Trees II

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

Given an integer 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.

Thoughts

分治的略繁琐应用。利用BST的性质，左子树范围都比给定的数小，右子树范围比给定的数大，假设当前函数返回给定范围的所有BST，那把所有左子树和右子树都组合一遍就是结果。

root可以是范围内的所有节点.

还可以用个map存储已经生成过的树的范围以避免重复生成

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<TreeNode> helper(int start, int end) {
        List<TreeNode> roots = new ArrayList<>();
        if (start > end) {
            return roots;
        }

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

        for (int i = start; i <= end; i++) {
            TreeNode root;
            List<TreeNode> lefts = helper(start, i - 1);
            List<TreeNode> rights = helper(i + 1, end);
            for (TreeNode left : lefts) {     
                for (TreeNode right : rights) {
                    root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    roots.add(root);
                }
                if (rights.isEmpty()) {
                    root = new TreeNode(i);
                    root.left = left;
                    roots.add(root);
                }
            }
            if (lefts.isEmpty()) {            
                for (TreeNode right : rights) {
                    root = new TreeNode(i);
                    root.right = right;
                    roots.add(root);
                }        
            }
        }

        return roots;
    }

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

Analysis

Errors:

1. new root(i)位置写错

2. 忘了考虑左右子树为空的情况。

3. 引入了不必要的map

Ver.2

https://discuss.leetcode.com/topic/2940/java-solution-with-dp

顺着它是在DP求Unique Binary Search Tree I 的思路, i为当前节点个数, j为当前root, 它左子树可以有f[j - 1]种树的形状, 分别就是前面f[j-1]对应生成的树; 右子树有f[i - j - 1]种形状, 它们形状和f[i - j-1]是一样的, 区别在于值, 每个节点相当于f[i - j -1]的树们的每个节点的值加上j + 1这个offset.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private TreeNode clone(TreeNode node, int offset) {
        if (node == null) {
            return null;
        }
        TreeNode newNode = new TreeNode(node.val + offset);
        newNode.left = clone(node.left, offset);
        newNode.right = clone(node.right, offset);
        return newNode;
    }

    public List<TreeNode> generateTrees(int n) {
        List<TreeNode>[] result = new List[n + 1];
        result[0] = new ArrayList<TreeNode>();
        if (n == 0) {
            return result[0];
        }

        result[0].add(null);
        for (int i = 1; i <= n; i++) {
            result[i] = new ArrayList<TreeNode>();
            for (int j = 0; j < i; j++) {
                for (TreeNode nodeL : result[j]) {
                    for (TreeNode nodeR : result[i - j - 1]) {
                        TreeNode node = new TreeNode(j + 1);
                        node.left = nodeL;
                        node.right = clone(nodeR, j + 1);
                        result[i].add(node);
                    }
                }
            }
        }

        return result[n];
    }
}

Analysis

时间复杂度应是每个1~N所对应的卡特兰数之和, Sigma_i (2i)!/[(i+1)!i!]