未分類

Find Mode in Binary Search Tree

Go, LeetCode, Tree

Find Mode in Binary Search Tree

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
  • The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
  • Both the left and right subtrees must also be binary search trees.

For example:

Given BST [1,null,2,2],

1
2
3
4
5
1
 \
  2
 /
2

return [2].

Note:

If a tree has more than one mode, you can return them in any order.

Follow up:

Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

提示 解題應用
Tree 中序遍歷

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

解答思路:

最簡單的方式就是使用hashmap來儲存，接著再檢查hashmap便能得知出現最多次是哪些元素了，不過Follow up希望我們能不使用額外的空間複雜度，一開始是用前序遍歷來看並做檢查，結果走了不少冤望路，因為除非相同的元素是連在一起，否則很難找出結果，例如下列的二元樹:

因為相同的元素可能分散的情況下就非常難做統計，所以看得出來使用前序遍歷是錯的選擇，而中序遍歷就會是最佳做法，因為中序遍歷二元樹出來的結果會是從小至大排序好的結果，如此一來便能很輕易的去做統計，附帶一提雖然採用遞回的方式不被認為算是使用額外的空間，但如果需要只用O(1)的空間來進行樹的遍歷可以使用: Morris Traversal演算法。

程式碼解說:

最主要是做中序遍歷，不過因為遍歷的上一個值也好，或者到目前為止統計出現次數，及最大的出現數等等都需要在遞回之間傳遞，因此需要用傳”址”而非傳”值”，如果節點為nil值就直接回傳結果，接下來便開始我們的中序遍歷，這邊我們一開始先中序遍歷左子節點，接著才處理我們的目標節點，最後才中序遍歷右子節點並回傳結果

1
2
3
4
5
6
7
8
func inOrderTravel(node *TreeNode, tmp *int, count *int, max *int, result []int) []int {
	if node == nil {
		return result
	}
	result = inOrderTravel(node.Left, tmp, count, max, result)
	...
	return inOrderTravel(node.Right, tmp, count, max, result)
}

這邊則處理我們的目標節點，一開始先看上一個遍歷節點的值是否與目標節點相同，若不同就將前一個暫存節點的值改為現在目標節點的值，以方便到下一個節點時能知道前一個節點的值變成多少，因為節點值變了所以此時將計數歸0，再將新節點的計數+1，當出現的次數超過最大次數就將其取代，並清空原本結果陣列所儲存出現次數較少的值再放入新的值，而最後如果出現的次數等同最大次數則直接將新的值放入結果陣列的後頭

1
2
3
4
5
6
7
8
9
10
11
if node.Val != *tmp {
	*tmp = node.Val
	*count = 0
}
*count++
if *count > *max {
	*max = *count
	result = []int{*tmp}
} else if *count == *max {
	result = append(result, *tmp)
}

完整程式碼:

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
func findMode(root *TreeNode) []int {
	var tmp int
	var max int
	var count int
	var result []int
	return inOrderTravel(root, &tmp, &count, &max, result)
}
func inOrderTravel(node *TreeNode, tmp *int, count *int, max *int, result []int) []int {
	if node == nil {
		return result
	}
	result = inOrderTravel(node.Left, tmp, count, max, result)
	if node.Val != *tmp {
		*tmp = node.Val
		*count = 0
	}
	*count++
	if *count > *max {
		*max = *count
		result = []int{*tmp}
	} else if *count == *max {
		result = append(result, *tmp)
	}
	return inOrderTravel(node.Right, tmp, count, max, result)
}

總結:

若要遍歷二元樹找出出現最多次的值有哪些，並且在不使用額外空間的情況下可以使用中序遍歷，因為中序遍歷二元樹的結果會是從小至大排序的結果，尤其是在統計相同值出現的次數會非常簡易，此外若有不採用遞回方式的需求來遍歷樹可以用Morris Traversal演算法。

分享到