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

成都創(chuàng)新互聯(lián)公司致力于網(wǎng)站建設(shè)、成都網(wǎng)站建設(shè),成都網(wǎng)站設(shè)計(jì),集團(tuán)網(wǎng)站建設(shè)等服務(wù)標(biāo)準(zhǔn)化，推過標(biāo)準(zhǔn)化降低中小企業(yè)的建站的成本，并持續(xù)提升建站的定制化服務(wù)水平進(jìn)行質(zhì)量交付，讓企業(yè)網(wǎng)站從市場競爭中脫穎而出。 選擇成都創(chuàng)新互聯(lián)公司，就選擇了安全、穩(wěn)定、美觀的網(wǎng)站建設(shè)服務(wù)！

給你一個(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] 會(huì)得到一棵不同的 BST 。

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

由于答案可能會(huì)很大，請將結(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ù)組會(huì)得到相同的 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ò)，可以把它分享出去讓更多的人看到吧！

標(biāo)題名稱：leetcode如何求將子數(shù)組重新排序得到同一個(gè)二叉查找樹的方案數(shù)
分享鏈接：http://jinyejixie.com/article38/pgsppp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站策劃、虛擬主機(jī)、云服務(wù)器、網(wǎng)站收錄、App設(shè)計(jì)、App開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)