95. Unique Binary Search Trees II

题目描述

Given n, how many structurally unique BST's(binary search trees) that store values 1...n?

For example,
Givenn= 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

解题方法

The resolution come to my mind is recursion.

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

    public List<TreeNode> generateTrees(int start,int end){             
        List<TreeNode> trees = new ArrayList<TreeNode>();
        if(start>end){  trees.add(null); return trees;}

        for(int rootValue=start;rootValue<=end;rootValue++){
            List<TreeNode> leftSubTrees=generateTrees(start,rootValue-1);
            List<TreeNode> rightSubTrees=generateTrees(rootValue+1,end);

            for(TreeNode leftSubTree:leftSubTrees){
                for(TreeNode rightSubTree:rightSubTrees){
                    TreeNode root=new TreeNode(rootValue);
                    root.left=leftSubTree;
                    root.right=rightSubTree;
                    trees.add(root);
                }
            }
        }
        return trees;
    }

The other way is using DP.