未分類

Unique Binary Search Trees II

DynamicProgramming, Go, LeetCode, Tree

Unique Binary Search Trees II

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example:

Given n = 3, your program should return all 5 unique BST’s shown below.

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

Default:

1
2
3
4
5
6
7
8
9
10
11
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func generateTrees(n int) []*TreeNode {
}

解答思路:

先前有一篇Unique Binary Search Trees是在計算n個節點的情況下能組出幾種不同的BST，但是這次是要回傳所有不同的組合而非單單個數而已，所以沒有辦法用上公式來處理，透過先前題目可以知道二元樹經過排序的情況下，隨著根節點的值不同，底下的對應組合就是左右子樹的問題，只是這次我們在乎的就不僅僅只是左右子樹的節點數有多少個，而是要實作出所有組合，要實作出所有組合就會用上遞回的方式處理，再想一想對於那些左右子數來說不也是一樣是一棵二元樹，也是先決定根節點再次分成左右子樹，所以對於遞回來說1~n的節點如果取k作為根節點，1~k-1及k+1~n就會是左右子樹的範圍，剩下就是不斷重覆上述行為直到取的根節點是nil為止便能找出所有組合。

程式碼解說:

一開始先將節點數為0的情況篩選掉，而因為接下來要透過遞回的方式不斷的在範圍之間取值來作為根節點，所以便以迴圈生成包含1~n的陣列，接著才將該陣列帶入遞回函數之中以取得所有組成的BST

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

再來就是處理遞回的部分，如果範圍為空就回傳一個包含nil的陣列位址，而之所以不回傳空的陣列是因為最後左右子節樹在與根節點做合併嫁接時，如果任一子樹不存在就假裝用nil節點位址在取代，以利後續能直接從左右子樹的陣列位址取值(空陣列就沒辦法取值來組合)來排列組合，範圍存在的話就先在最外層用迴圈一一取出範圍中的值以分別來做為二元樹的根節點，接著如先前思路所述如果取k作為根節點，1~k-1及k+1~n就會是左右子樹的範圍，就分別再將其再次帶入遞回以找出左右子樹的所有組合，待左右子樹的所有組合回來後，用巢狀迴圈來將左右子樹的所有組合再次進行排列組合，同時新增根節點將左右子樹嫁接並放入結果之中，最後等到範圍內的所有值一一做為根節點進而找出旗下的所有組合之後才向上回傳結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func combine(candidates []int) []*TreeNode {
	if len(candidates) == 0 {
		return []*TreeNode{nil}
	}
	var new *TreeNode
	var left []*TreeNode
	var right []*TreeNode
	var result []*TreeNode
	for i, v := range candidates {
		left = combine(candidates[:i])
		right = combine(candidates[i+1:])
		for _, lv := range left {
			for _, rv := range right {
				new = &TreeNode{v, lv, rv}
				result = append(result, new)
			}
		}
	}
	return result
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func generateTrees(n int) []*TreeNode {
	if n == 0 {
		return []*TreeNode{}
	}
	candidates := make([]int, n)
	for i := 1; i <= n; i++ {
		candidates[i-1] = i
	}
	return combine(candidates)
}
func combine(candidates []int) []*TreeNode {
	if len(candidates) == 0 {
		return []*TreeNode{nil}
	}
	var new *TreeNode
	var left []*TreeNode
	var right []*TreeNode
	var result []*TreeNode
	for i, v := range candidates {
		left = combine(candidates[:i])
		right = combine(candidates[i+1:])
		for _, lv := range left {
			for _, rv := range right {
				new = &TreeNode{v, lv, rv}
				result = append(result, new)
			}
		}
	}
	return result
}

總結:

若有n個節點要組成BST，列出所有能組出的BST，要實作出所有組合就會用上遞回的方式處理，對於遞回來說1~n的節點如果取k作為根節點，1~k-1及k+1~n就會是左右子樹的範圍，剩下就是不斷重覆上述行為直到取的根節點是nil為止便能找出所有組合。

分享到