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

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

給你一個(gè)數(shù)組 nums 表示 1 到 n 的一個(gè)排列。我們按照元素在 nums 中的順序依次插入一個(gè)初始為空的二叉查找樹（BST）。請你統(tǒng)計(jì)將 nums 重新排序后，統(tǒng)計(jì)滿足如下條件的方案數(shù)：重排后得到的二叉查找樹與 nums 原本數(shù)字順序得到的二叉查找樹相同。

比方說，給你 nums = [2,1,3]，我們得到一棵 2 為根，1 為左孩子，3 為右孩子的樹。數(shù)組 [2,3,1] 也能得到相同的 BST，但 [3,2,1] 會得到一棵不同的 BST 。

請你返回重排 nums 后，與原數(shù)組 nums 得到相同二叉查找樹的方案數(shù)。

由于答案可能會很大，請將結(jié)果對 10^9 + 7 取余數(shù)。

示例 1：

輸入：nums = [2,1,3]

輸出：1

解釋：我們將 nums 重排， [2,3,1] 能得到相同的 BST 。沒有其他得到相同 BST 的方案了。

示例 2：

輸入：nums = [3,4,5,1,2]

輸出：5

解釋：下面 5 個(gè)數(shù)組會得到相同的 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 的方案數(shù)是 3216212999。將它對 10^9 + 7 取余后得到 216212978。

提示：

1 <= nums.length <= 1000

1 <= nums[i] <= nums.length

nums 中所有數(shù) 互不相同 

解題思路

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

2，搜索樹的性質(zhì)，左節(jié)點(diǎn)<根<右節(jié)點(diǎn)

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

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

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

6，假設(shè)左樹節(jié)點(diǎn)為m，右樹為n

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

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

代碼實(shí)現(xiàn)

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}

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