Dark Theme License

The MIT License (MIT)

Copyright © 2022-2023 Lumynous

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

1569. Number of Ways to Reorder Array to Get Same BST

題目連結: Leetcode

題目概要

關於二元搜尋樹

給一能構二元搜尋樹的數列, 問除原數列外還有幾種排法能建構出相同的二元樹

想法

DFS + 組合數

題目給一個數列並以索引值0為根節點
則剩下的數字要分成左右子樹
若左子樹的數字量為 n 則右子樹的數字量為 m = vec.size()-1-n
將左子樹的值視為相同物(右子樹同理)
那麼總共vec.size()-1個數字的排列方法共

$C_n^{n+m}$

sample

舉數列{6, 3, 2, 5, 8, 9, 4}為例
除了根節點6外
左子樹為: 3, 2, 5, 4 共4個小於根節點
右子樹為: 8, 9 共2個大於根節點
則小於根節點與大於根節點的組合為

$C_2^6$ 或

$C_4^6$

接著遞迴求出左右子樹個別子節點的組合數
因為過程中需要大量計算組合數, 因此可以先列出巴斯卡三角形來快速查詢

$C_m^n$ 的值

參考解法

歡迎補充

C++ DFS

class Solution {
private:
    int MOD = 1e9+7;
    vector<vector<int>> table;
    vector<vector<int>> Pascal_triangle(int n){
        vector<vector<int>> table(n+1);
        for (int i=0; i<=n; i++){
            table[i].resize(i+1);
            table[i][0] = 1;
            table[i][i] = 1;
            for (int j=1; j<i; j++){
                table[i][j] = (table[i-1][j-1] + table[i-1][j]) % MOD;
            }
        }
        return table;
    }

    long long dfs(vector<int> &nums){
        int n = nums.size();
        if (n < 3) return 1;
        int root = nums[0];
        vector<int> left, right;
        for (auto i: nums){
            if (i < root) left.push_back(i);
            else if (i > root) right.push_back(i);
        }

        return (((dfs(left) % MOD * dfs(right) % MOD) % MOD) * table[n - 1][left.size()]) % MOD;
    }

public:
    int numOfWays(vector<int>& nums) {
        int n = nums.size();
        table = Pascal_triangle(n);
        return (dfs(nums)-1) % MOD;
    }
};

---

Dark Theme License

The MIT License (MIT)

Copyright © 2022 Luminous-Coder

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.