未分類

Convert Sorted Array to Binary Search Tree

DepthFirstSearch, Go, LeetCode, Tree

Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

提示 解題應用
DepthFirstSearch InorderTravel

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 sortedArrayToBST(nums []int) *TreeNode {
}

解答思路:

如果知道二元搜尋樹經過中序遍歷得到的結果會是由小至大排序好的陣列，而且中序遍歷的結果陣列如果隨意指定任意值作為根節點的值，該根節點左邊全部的值就是左子樹的節點值，右邊全部的值就是右子樹的節點值，那麼現在給你一個小至大排序好的陣列，要還原成二元搜尋樹就不是什麼大問題，唯一要注意的就是要指定哪個值作為根節點就是問題所在，根據敘述可以得知該二元搜尋樹同時也要是一棵平衡樹，即然這樣當然每次就只挑陣列最中間的值來做為根節點，如此一來最後的二元搜尋樹就肯定會是平衡樹，至於如果陣列值的數量是偶數的話，本題是以中間偏後主為主，如[1,2,3,4]則取3作為根節點。

程式碼解說:

如果知道了中序遍歷與排序陣列間關係的話，就直接將由小至大排序好的陣列帶入遞回函數之中來還原回二元搜尋樹

1
2
3
func sortedArrayToBST(nums []int) *TreeNode {
	return construct(nums)
}

接下來就是遞回還原二元樹的處理，如果進來的排序陣列為空，表示此節點不存在直接回傳nil位址，而如果不為空則從陣列中取出中間的值作為根節點值(這邊直接將陣列長度除以2來作為index)，並記得將根節點值左側全部帶入左子樹，根節點值右側全部帶入右子樹，分別再次往下遞回，待兩側子樹的位址回來，最後才向上回傳新建的根節點位址並嫁接左右子樹

1
2
3
4
5
6
7
8
9
func construct(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}
	rootIndex := len(nums) / 2
	left := construct(nums[:rootIndex])
	right := construct(nums[rootIndex+1:])
	return &TreeNode{nums[rootIndex], left, right}
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
func sortedArrayToBST(nums []int) *TreeNode {
	return construct(nums)
}
func construct(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}
	rootIndex := len(nums) / 2
	left := construct(nums[:rootIndex])
	right := construct(nums[rootIndex+1:])
	return &TreeNode{nums[rootIndex], left, right}
}

總結:

要將一個小至大排序好的陣列還原成二元搜尋、平衡樹的話，每次只挑陣列最中間的值來做為根節點，其中該根節點左邊全部的值就是左子樹的節點值，右邊全部的值就是右子樹的節點值，最後透過遞回不斷重覆上述動作便能順利將排序陣列還原回二元搜尋、平衡樹。

分享到