题目

leetcode:501

代码与解析

最笨拙的方式

用hash表来存储每一个值，极其笨拙，按普通二叉树做
相信不止我一个想对map中的value排序，不过，这个真做不到。C++中如果使用std::map或者std::multimap可以对key排序，但不能对value排序。
所以可以把map转化数组，再进行排序，当然数组里面放的也是pair<int, int>类型的数据，第一个int为元素，第二个int为出现频率。

func findMode(root *TreeNode) []int {
    if root==nil{
        return []int{}
    }
    m := map[int]int{}

    var traversal func(root *TreeNode)
    traversal = func (root *TreeNode){
        if root==nil{
            return
        }
        m[root.Val]++
        traversal(root.Left)
        traversal(root.Right)
    }
    traversal(root)

    r := []int{}
    max_key := []int{}
    // 一坨屎山，暂时不知道如果这种方法怎么优化
    for _,k := range m{
        r = append(r, k)
    }
    sort.Ints(r)

    max := r[len(r)-1]

    for k, v := range m{
        if v==max{
            max_key = append(max_key, k)
        }
    }
    return max_key
}

中序遍历

如果是头结点，那么count等于1
不是头结点的话上一个节点值和现节点相等，count++
两个节点不相等的时候， count等于1

// 头结点
if pre==nil{
    count = 1
}else if pre.Val==root.Val{ // 如果值等于上一个值，count++
    count++
}else{
    // 值不相等
    count = 1
}

如果count和maxCount相等，添加进数组

// 相等就添加进res，可能不止有一个元素，可能很多个频率都相等，所以此处这么判断，如果当前频率等于已有记录的最大频率，就添加进数组。
if count==maxCount{
    res = append(res, root.Val)
}

如果count 大于 maxCount的时候，不仅要更新maxCount，而且要清空结果集res

// 更新pre节点
pre = root
// 如果当前count大，那么就要清空res,然后更新maxCount
if count>maxCount{
    res = []int{}
    // 更新最大频率
    maxCount = count
    res = append(res, root.Val)
}

代码：

func findMode(root *TreeNode) []int {
    var pre *TreeNode
    count := 0
    maxCount := 0
    res := []int{}
    var traversal func (root *TreeNode)
    traversal = func (root *TreeNode){
        if root==nil{
            return 
        }
        // 中序遍历
        traversal(root.Left)  // 左
        // 处理中间节点
        // 头结点
        if pre==nil{
            count = 1
        }else if pre.Val==root.Val{ // 如果值等于上一个值，count++
            count++
        }else{
            // 值不相等
            count = 1
        }
        // 相等就添加进res
        if count==maxCount{
            res = append(res, root.Val)
        }
        // 更新pre节点
        pre = root
        // 如果当前count大，那么就要清空res,然后更新maxCount
        if count>maxCount{
            res = []int{}
            // 更新最大频率
            maxCount = count
            res = append(res, root.Val)
        }
        // 右
        traversal(root.Right)
        return 
    }
    traversal(root)
    return res
}