Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

&nbsp;
Example 1:

Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]


Example 2:

Input: n = 1
Output: [[1]]


&nbsp;
Constraints:


	1 &lt;= n &lt;= 8


# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:

    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        # define a sorted list of the numbers, for each num in that list , leftvalues
# are left tree and right val are rightree, then for each number create a tree
# assign the left and right to that root and append the root to the ans
        nums = list(range(1,n+1))
        def dfs(nums):
            if not nums:
                return [None]
            ans = []
            for i in range(len(nums)):
                leftTrees = dfs(nums[:i])
                rightTrees = dfs(nums[i+1:])

                for l in leftTrees:
                    for r in rightTrees:
                        root = TreeNode(nums[i])
                        root.left = l
                        root.right = r
                        ans.append(root)
            return ans

        return dfs(nums)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        return helper(1,n);
    }
    
    public List<TreeNode> helper(int lo, int hi){
        List<TreeNode> res=new ArrayList<>();
        if(lo>hi){
            res.add(null);
            return res;
        }
        
        
        for(int i=lo;i<=hi;i++){
            List<TreeNode> left=helper(lo,i-1);
            List<TreeNode> right=helper(i+1,hi);
            
            for(TreeNode l:left){
                for(TreeNode r:right){
                    TreeNode head=new TreeNode(i);
                    head.left=l;
                    head.right=r;
                    
                    res.add(head);
                }
            }
        }
        
        return res;
    }
}
class Solution 
{
    public:
    vector<TreeNode*> solve(int start, int end)
    {
        //base case
        if(start>end){
            return {NULL};
        }
        vector<TreeNode*> lChild, rChild, res;
        //forming a tree, by keeping each node as root node
        for(int i=start; i<=end; i++)
        {
            //don't create node here, bcz for each combination of subtree, node with new address has to be generated

            //recursive call for left,right child, they will return vector of all possible subtrees
            lChild = solve(start, i-1);
            rChild = solve(i+1, end);
            
            //for each subtree returned by lChild, forming combination with each subtree returned by rChild
            for(auto l: lChild)
            {
                for(auto r: rChild)
                {
                    //generating new node for each combination
                    TreeNode* node = new TreeNode(i);
                    //attaching left, right childs
                    node->left = l;
                    node->right = r;
                    res.push_back(node);
                }
            }            
        }
        //returning all possible subtrees
        return res;
    }
    vector<TreeNode*> generateTrees(int n) {
        return solve(1, n);
    }
};
var generateTrees = function(n) {
    if(n <= 0){
        return [];
    }
    return generateRec(1, n);

};

function generateRec(start, end){
    let result = [];

    if(start > end){
        result.push(null);
        return result;
    }

    for(let i = start; i <end+1; i++){
        let left = generateRec(start, i-1);
        let right = generateRec(i+1, end);

        for(let l = 0; l < left.length; l++){
            for(let r = 0; r < right.length; r++){
                let root = new TreeNode(i,left[l], right[r]);
                result.push(root);
            }
        }

    }
    return result;

}
Unique Binary Search Trees II