// @Title: 不同的二叉搜索树 II (Unique Binary Search Trees II)
// @Author: qisiii
// @Date: 2024-09-17 14:04:50
// @Runtime: 1 ms
// @Memory: 43.4 MB
// @comment: 
// @flag: 
/**
 * 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) {
        int[] arr=new int[n];
        for(int i=1;i<=n;i++){
            arr[i-1]=i;
        }
       return generateTrees(arr,0,n-1);
    }
    private static List<TreeNode> generateTrees(int[] nums,int left,int right){
        List<TreeNode> result=new ArrayList<>();
        if(left==right){
            result.add(new TreeNode(nums[left]));
            return result;
        }
        for(int i=left;i<=right;i++){
            if(i>left&&i<right){
                List<TreeNode> lefts=generateTrees(nums,left,i-1);
                List<TreeNode> rights=generateTrees(nums,i+1,right);
                for(TreeNode leftNode:lefts){
                    for(TreeNode rightNode:rights){
                        TreeNode temp=new TreeNode(nums[i]);
                        temp.left=leftNode;
                        temp.right=rightNode;
                        result.add(temp);
                    }
                }
            }
            else if(i==right){
                List<TreeNode> lefts=generateTrees(nums,left,i-1);
                for(TreeNode node:lefts){
                    TreeNode root=new TreeNode(nums[i]);
                    root.left=node;
                    result.add(root);
                }
            }
            else if(i==left){
                List<TreeNode> rights=generateTrees(nums,i+1,right);
                for(TreeNode node:rights){
                    TreeNode root=new TreeNode(nums[i]);
                    root.right=node;
                    result.add(root);
                }

            }

        }
        return result;
    }
}