未分類

Kth Smallest Element in a BST

BinarySearch, Go, LeetCode, Tree

Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:

You may assume k is always valid, 1 ? k ? BST’s total elements.

Follow up:

What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

提示 解題應用
Tree 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 kthSmallest(root *TreeNode, k int) int {
}

解答思路:

如果有一棵二元搜尋樹要找出第k個大的元素，基本上就只要透過中序遍歷就會得到一個由小排序至大的數列，此時再根據題目所需找出第k個大的目標，數列所對應到的第k個位置就會是我們要的結果。

程式碼解說:

如思路所述，一開始便透過中序遍歷(由遞回函數實作，第一個參數為節點的位置，而第二個參數則是目前已排序的數列)來從二元搜尋樹取得所有節點值由小排序至大的數列，有了排序數列的話，最後再根據所需目標找出對應數列中的第k個位置就會是我們要的結果

1
2
3
4
func kthSmallest(root *TreeNode, k int) int {
	sortList := inOrderTravel(root, []int{})
	return sortList[k-1]
}

至於實作中序遍歷的遞回函數細節，先檢查帶入的節點是否為nil，如果是便直接向上回傳原本所帶入的排序數列，否則繼續向下做中序遍歷，將左子節點與數列帶入遞回函數得到新的數列之後，再對目前的節點做處理(將節點值放入數列後頭)，接著才是將右子節點與數列帶入遞回函數，最後如果節點與其左右子樹的值都處理完畢，便向上回傳整個排序數列

1
2
3
4
5
6
7
8
9
func inOrderTravel(node *TreeNode, list []int) []int {
	if node == nil {
		return list
	}
	list = inOrderTravel(node.Left, list)
	list = append(list, node.Val)
	list = inOrderTravel(node.Right, list)
	return list
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
func kthSmallest(root *TreeNode, k int) int {
	sortList := inOrderTravel(root, []int{})
	return sortList[k-1]
}
func inOrderTravel(node *TreeNode, list []int) []int {
	if node == nil {
		return list
	}
	list = inOrderTravel(node.Left, list)
	list = append(list, node.Val)
	list = inOrderTravel(node.Right, list)
	return list
}

總結:

若二元搜尋樹要找出第k個大的元素，基本上就只要透過中序遍歷就會得到一個由小排序至大的數列，此時再根據題目所需找出第k個大的目標，數列所對應到的第k個位置就會是我們要的結果。

分享到