[java/3ms] DP, using list<TreeNode>[]


  • 0

    From Unique BST 1, we have DP transformation formula, BST[i] = sum{BST[j] + BST[i-1-j]}, for j = 0...i-1. That is, #BST with j nodes on left + #BST with i-1-j nodes on right, regardless of the actual values in the BST.

    But here, we have to care about the actual tree value. So, I use offset on trees I've already generated.

    template[i] means all possible BSTs generated from 0...i, for further understanding, you can think it just as BST with i nodes.

    public List<TreeNode> generateTrees(int n) {
            if (n < 1)
                return new ArrayList<>();
            
            List<TreeNode>[] template = new ArrayList[n+1];
            List<TreeNode> zero = new ArrayList<>();
            zero.add(null);
            template[0] = zero;
            
            for (int i = 1; i <= n; i++) {
                List<TreeNode> tmp = new ArrayList<>();
                for (int j = 0; j < i; j++) {
                    for (TreeNode left_root : template[j]) {
                        for (TreeNode right_root: template[i-1-j]) {
                            TreeNode root = new TreeNode(j+1);
                            root.left = generator(left_root, 0);
                            root.right = generator(right_root, j+1);
                            tmp.add(root);
                        }
                    }
                }
                template[i] = tmp;
            }
            
            return template[n];
        }
        
        private TreeNode generator(TreeNode root, int offset) {
            if (root == null)
                return root;
            TreeNode _root = new TreeNode(root.val + offset);
            _root.left = generator(root.left, offset);
            _root.right = generator(root.right, offset);
            return _root;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.