1         3     3      2      1

    \       /     /      / \      \

     3     2     1      1   3      2

    /     /       \                 \

   2     1         2                 3

 /**

  * Definition for binary tree

  * public class TreeNode {

  *     int val;

  *     TreeNode left;

  *     TreeNode right;

  *     TreeNode(int x) { val = x; left = null; right = null; }

  * }

  */

 public class Solution {

     private ArrayList<TreeNode> generate(int start,int end){

         ArrayList<TreeNode> answer = new ArrayList<TreeNode>();

         if(start > end){

             answer.add(null);

             return answer;

         }

         //for every node from start to right,make it as tree root and recursively build its left and right child tree

         for(int i = start; i <= end;i++){

             ArrayList<TreeNode> left = generate(start, i-1);

             ArrayList<TreeNode> right = generate(i+1, end);

             for(TreeNode l:left){

                 for(TreeNode r:right){

                     TreeNode root = new TreeNode(i);

                     root.left = l;

                     root.right = r;

                     answer.add(root);

                 }

             }

         }

         return answer;

     }

     public List<TreeNode> generateTrees(int n) {

         return generate(1,n);

     }

 }