1569. 将子数组重新排序得到同一个二叉查找树的方案数 数学+DFS

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;
        }
    }
}