题目

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
}
分类: 算法

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

站点统计

  • 文章总数:304 篇
  • 分类总数:19 个
  • 标签总数:189 个
  • 运行天数:852 天
  • 访问总数:459493 人次
ICP备案号: 辽ICP备20003309号