力扣二叉树--第三十八天

前言

后面几天准备期末考试，要断更了。8号or 9号再开始。

内容

一、二叉搜索树中的众数

501. 二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

• 结点左子树中所含节点的值 小于等于 当前节点的值
• 结点右子树中所含节点的值 大于等于 当前节点的值
• 左子树和右子树都是二叉搜索树

中序遍历

第一想法是遍历二叉树，把各结点放入哈希表中记录出现的次数。但这是二叉搜索树，第一想法应该是中序遍历！遍历后他是一个有序数组。相邻两个元素作比较，然后就把出现频率最高的元素输出。注意，可能有多个众数！

func findMode(root *TreeNode) []int {
    res:=make([]int,0)
    var prev *TreeNode
    count:=1
    max:=1
    var travel func(node *TreeNode)
    travel=func(node *TreeNode){
        if node==nil{
            return 
        }
        travel(node.Left)
       if prev!=nil&&prev.Val==node.Val{
           count++
       }else{
           count=1
       }
       if count>=max{
           if count>max&&len(res)>0{
               res=[]int{node.Val}
           }else{
               res=append(res,node.Val)
           }
           max=count//更新max
       }
       prev=node
       travel(node.Right)
    }
    travel(root)
    return res
}

最后

做好当下，拒绝焦虑！