题目
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
/
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).
解题思路
遍历二叉树，将所有节点的值和出现的次数放入map中，找到出现次数最多的值，输出
代码
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
var numMap map[int]int
func preOrderTravel(t *TreeNode) {
if nil == t {
return
}
numMap[t.Val]++
preOrderTravel(t.Left)
preOrderTravel(t.Right)
}
func findMode(root *TreeNode) []int {
numMap = make(map[int]int)
preOrderTravel(root)
fmt.Printf("numMap:%+v\n", numMap)
type Mode struct {
time int
val int
}
var maxMode []Mode
for v, time := range numMap {
if len(maxMode) == 0 || time > maxMode[0].time {
tmpMode := Mode{time, v}
maxMode = []Mode{tmpMode}
} else if time == maxMode[0].time {
tmpMode := Mode{time, v}
maxMode = append(maxMode, tmpMode)
}
}
fmt.Printf("maxMode:%+v\n", maxMode)
var ret []int
for _, v := range maxMode {
ret = append(ret, v.val)
}
return ret
}
