题目

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 
}