1569. 将子数组重新排序得到同一个二叉查找树的方案数
给你一个数组 nums 表示 1 到 n 的一个排列。我们按照元素在 nums 中的顺序依次插入一个初始为空的二叉查找树（BST）。请你统计将 nums 重新排序后，统计满足如下条件的方案数：重排后得到的二叉查找树与 nums 原本数字顺序得到的二叉查找树相同。
比方说，给你 nums = [2,1,3]，我们得到一棵 2 为根，1 为左孩子，3 为右孩子的树。数组 [2,3,1] 也能得到相同的 BST，但 [3,2,1] 会得到一棵不同的 BST 。
请你返回重排 nums 后，与原数组 nums 得到相同二叉查找树的方案数。
由于答案可能会很大，请将结果对 10^9 + 7 取余数。
示例 1：
输入：nums = [2,1,3] 输出：1 解释：我们将 nums 重排， [2,3,1] 能得到相同的 BST 。没有其他得到相同 BST 的方案了。
示例 2：
输入：nums = [3,4,5,1,2] 输出：5 解释：下面 5 个数组会得到相同的 BST： [3,1,2,4,5] [3,1,4,2,5] [3,1,4,5,2] [3,4,1,2,5] [3,4,1,5,2]
示例 3：
输入：nums = [1,2,3] 输出：0 解释：没有别的排列顺序能得到相同的 BST 。
示例 4：
输入：nums = [3,1,2,5,4,6] 输出：19
示例 5：
输入：nums = [9,4,2,1,3,6,5,7,8,14,11,10,12,13,16,15,17,18] 输出：216212978 解释：得到相同 BST 的方案数是 3216212999。将它对 10^9 + 7 取余后得到 216212978。
提示：
- 1 <= nums.length <= 1000
- 1 <= nums[i] <= nums.length
- nums 中所有数互不相同。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-ways-to-reorder-array-to-get-same-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
做题结果
大概算是成功吧，已经吧组合公式+合成方式推导出来了，然后心想着，不可能这么难吧？看了题目确实用组合，然后没看答案推出来。
方法：数学+DFS
首先对于左边右边各有几个元素的情况，放置方式种类数，需要考虑。
1. 假设左右子树都是链，那么必然是从上到下排的。那有几种呢？假设大写是左子树，小写是右子树，字母顺序代表大小的话，可能是这样排：AabBcC,也就是是说，同一边的顺序是一致的。这种情况，我们可以忽略数值的影响，看成XyyXyX,本质上，是把3个X放入长度为6，共有几种方法的组合数
2. 然后我们可以考虑复杂一些的情况，也就是左边是链，假设长度是3，右边是 a为根，bc为左右子树，又怎么排呢？放置ABC的方式不变，依然可以看做XyyXyX，6选3的组合数。不同的是，y产生了一定的顺序。bc的顺序可以变化了。可以是abc或者acb，也就是两种情况,右侧排序数量2，合起来就是C(6,3)*2，组合数乘以右边获得的总路径数即为答案
3. 如果两边都是完整的树呢？那左侧X的排序，也可以不止一种了，根据左侧路径即可
4. 综上，对于当前节点，path=C(lenLeft+lenRight,leftLeft)*pathLeft*pathRight
5. 所以当前节点路径数目，由子节点的节点数目+路径数目合成，当前节点作为根节点的总节点数目为 lenLeft+lenRight+1,也就成功通过子问题合成当前问题，实现了DFS
6. 结束条件：空节点的路径为1，节点数0，叶子节点路径1，节点1
class Solution {static final int CSIZE = 2000;
static final int MOD = (int) (1e9+7);
static long[][] C = new long[CSIZE+1][CSIZE+1];
static{
C[0][0] = 1;
for(int i = 1; i < CSIZE+1; i++){
C[i][0] =1;
for(int j = 1; j <= i; j++){
C[i][j] = (C[i-1][j]+C[i-1][j-1])%MOD;
}
}
}
public int numOfWays(int[] nums) {
Node head = new Node(nums[0]);
int n = nums.length;
for(int i = 1; i < n; i++){
insert(head,nums[i]);
}
int ans = (int) ((dfs(head)[0]+MOD-1)%MOD);
return ans;
}
private void insert(Node head, int val){
if(val<head.val){
if(head.left == null) head.left=new Node(val);
else insert(head.left,val);
}else{
if(head.right==null) head.right = new Node(val);
else insert(head.right,val);
}
}
//path/cnt
private long[] dfs(Node root){
if(root == null) return new long[]{1,0};
if(root.left == null && root.right == null) return new long[]{1,1};
long[] a = dfs(root.left);
long[] b = dfs(root.right);
long path = C[(int)(a[1]+b[1])][(int)a[1]]*a[0]%MOD*b[0]%MOD;
return new long[]{path,a[1]+b[1]+1};
}
class Node{
Node left;
Node right;
int val;
public Node(int val){
this.val = val;
}
}
}