leetcode如何求將子數組重新排序得到同一個二叉查找樹的方案數

這篇文章給大家分享的是有關leetcode如何求將子數組重新排序得到同一個二叉查找樹的方案數的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

給你一個數組 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 中所有數 互不相同 

解題思路

1，這個題目是組合排列＋搜索樹的組合題目

2，搜索樹的性質，左節點<根<右節點

3，我們可以把樹拆成左、根、右三部分

4，只要不改變左樹內部元素的相對位置和右樹內部元素的相對位置，搜索樹不變

5，因此變成了排列組合問題

6，假設左樹節點為m，右樹為n

7,總個數為: C(len(m+n),len(m))*f(m)*f(n)

8,最后還需要把自己剪掉

代碼實現

func numOfWays(nums []int) int {   return (getAllCount(nums)%1000000007-1+1000000007)%1000000007}
func split(nums[]int)([]int,[]int){    var l,r []int    for i:=1;i<len(nums);i++{        if nums[i]<nums[0]{            l=append(l,nums[i])        }else{            r=append(r,nums[i])        }    }    return l,r}
func getAllCount(nums []int) int{    if len(nums)<1{        return 1    }    l,r:=split(nums)    s:=way(len(l),len(r))    return (s*getAllCount(l)%1000000007)*getAllCount(r)%1000000007}
func way(l,r int)int{    sum:=1    for i:=1;i<=l;i++{        sum=(sum*(r+i)/i)%1000000007    }    return sum}

感謝各位的閱讀！關于“leetcode如何求將子數組重新排序得到同一個二叉查找樹的方案數”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！