未分類

Unique Binary Search Trees

DynamicProgramming, Go, LeetCode, Tree

Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example:

Given n = 3, there are a total of 5 unique BST’s.

1
2
3
4
5
1         3     3      2      1
 \       /     /      / \      \
  3     2     1      1   3      2
 /     /       \                 \
2     1         2                 3
提示 解題應用
DynamicProgramming 規律觀查

Default:

1
2
3
func numTrees(n int) int {
}

解答思路:

這題一開始可以說是根本毫無頭緒，參考別人的思路似乎還是有點一知半解，所以最初就先試著完全理解題目也許就能透過這樣的方式來發現規律，仔細觀查範例會發現不僅僅單純是二元樹，該二元樹還有經過排序，隨著根節點的值不同，底下的對應組合就很單純(因為沒有重覆值，依大小排就固定那幾種)，也就是說在有排序的情況下我們只在乎因為根節點的值而造成左右子節點分別有多少個就好(比該值小的有多少個，而比該值大的又有多少個)，在知道了兩邊各有多少個之後，如果同意整個二元樹組合總數是根節點的左右子樹分別的組合數相乘，那麼n的所有BST組合是由1~n的每個元素當作根節點的二元樹組合總數相加，其中每個二元樹組合總數又是由左右子樹分別的組合數相乘，最後推出:

f(0) = 1 (沒半個節點就只算1種組合)

f(n) = f(0)*f(n-1) + f(1)*f(n-2) + … + f(n-2)*f(1) + f(n-1)*f(0)

(第一組因為根節點是最小值開始，所以左側節點數為0，右側節點數為n-1…以此類推)

最後再有了公式作為結論之後，剩下就只是將公式實作而已。

程式碼解說:

透過公式可以知道要求出n個節點共能組出幾種不同的BST之前，要先求出0~n-1個節點的情況下能組出幾種不同的BST，所以一開始就先以一陣列來儲存0~n各種不同節點數的情況下所有不同BST的組合有多少種，因為已經知道了沒有個節點就只算1種組合，就在index為0的位置放入1，接著才開始以巢狀迴圈找出n個節點的組合總數，最外層的迴圈的index最主要是用來指向陣列中尚待求值的位置1~n，而內層的迴圈則是實作公式f(k)，也就是將每個元素當作根節點的二元樹組合總數累加至陣列index為k之中，最後陣列index為n的值就是我們要的結果

1
2
3
4
5
6
7
8
dp := make([]int, n+1)
dp[0] = 1
for i := 1; i <= n; i++ {
	for j := 0; j < i; j++ {
		dp[i] += dp[j] * dp[i-j-1]
	}
}
return dp[n]

完整程式碼:

1
2
3
4
5
6
7
8
9
10
func numTrees(n int) int {
	dp := make([]int, n+1)
	dp[0] = 1
	for i := 1; i <= n; i++ {
		for j := 0; j < i; j++ {
			dp[i] += dp[j] * dp[i-j-1]
		}
	}
	return dp[n]
}

總結:

若有n個節點要組成BST，找出共能組出幾種不同的BST，在二元樹還有經過排序的情況下就只關注因為根節點的值而造成左右子節點分別有多少個就好，接著如果同意整個二元樹組合總數是根節點的左右子樹分別的組合數相乘，那麼n的所有BST組合是由1~n的每個元素當作根節點的二元樹組合總數相加，其中每個二元樹組合總數又是由左右子樹分別的組合數相乘，最後推出公式:

f(n) = f(0)*f(n-1) + f(1)*f(n-2) + … + f(n-2)*f(1) + f(n-1)*f(0)

分享到