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

题目

核心思路

这道题最主要的就是理解二叉搜索树(BST)的插入原理，然后就要通过数学计算排列组合可能了，直接上图解分析即可。

根据二叉搜索树(BST)的定义，以及插入过程，可以发现，第一个元素作为根节点，必须是确定不变的，又因为二叉搜索树规定了其左边元素均小于它本身，它右边元素均大于它本身，也就是说，确定根节点后，左子树有哪些结点、右子树有哪些结点都确定了，既然如此，我们可以将除了根节点以外的结点分为：左子树的结点与右子树的结点 两类，这样两类结点就相互独立互不影响了，左子树和右子树之间的顺序可以任意交叉(PS:如果来了一个结点属于左子树，那么他肯定不会插入到右子树，故不会相互影响 )
所以，所有的可能种数就是：左右子树间的排列 * 左子树的可能性 * 右子树的可能性，而 左子树的可能性 和 右子树的可能性 恰好是原问题的子问题，所以把他交给递归处理即可，需要解决的就是 左右子树间的排列 了

参考上例，除了根节点剩余4个结点，左右子树间互不影响所以可以把左子树看成L结点，右子树看成R结点，他们的排列也就是总共四个位置，选出2个位置来放L结点，剩下2个位置来放R结点即可：C₄² = 6 (也就是相当于下标为n - 1，上标为比根节点小的结点个数)
综上，只要我们提前求出范围内的组合数(使用杨辉三角递推)，然后递归计算即可。

完整代码

class Solution {

    private int[][] C;// 存储组合数
    private final int MOD = (int) 1e9 + 7;

    public int numOfWays(int[] nums) {
        int n = nums.length;
        C = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    C[i][j] = 1;
                } else {
                    C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
                }
            }
        }

        return (f(nums) + MOD - 1) % MOD;
    }

    private int f(int[] nums) {
        if (nums == null || nums.length == 0)
            return 1;
        int n = nums.length;
        int k = nums[0];
        int[] left = new int[k - 1], right = new int[n - k];// 左右子数组
        int li = 0, ri = 0;// 左右数组下标
        for (int i = 1; i < n; i++) {
            if (nums[i] > k) {
                right[ri++] = nums[i] - k;// 将数据按原大小和顺序与下标对齐
            } else {
                left[li++] = nums[i];
            }
        }

        return (int) ((long) C[n - 1][k - 1] * f(left) % MOD * f(right) % MOD);
    }
}

这里有三个需要注意的细节

在给定范围内，组合数是可能超过数据范围的，所以可以提前使它对MOD取模，保证数据在int范围内
在使用组合数的时候，第一次乘上f(left也有可能越界，所以事先强转为long保证数据的正确性。
由于使用组合数C[n - 1][k - 1]时，比k小的数选用 k - 1 ，也就是认为每个nums都是从1到n的，所以可以在更新右子树数组时将元素与下标对齐(nums[i] - k)
剩下的内容就是交给递归，靠递归来分割左子树和右子树计算结果即可。

总结

又是一道数学题，唉，高中我还挺喜欢数学的，可上了大学就越来越不行了，做题时候也是好多一般性的问题找不到突破点，只能一点点学习学习这样的思路了。
如果文章有写的不正确的地方还请指出。感恩相遇~~~