题目链接:
题意:
给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。
如果树中有不止一个众数,可以按 任意顺序 返回。
解题思路:
递归法
由于是二叉搜索树,中序遍历是有序的,因此相当于在一个有序的数组上找出众数,利用有序的特性,在遍历二叉树的过程中,
标记上一个节点值 pre
(用于判断当前节点是否与上一个节点相同,相同,则众数 +1),当前的众数 conut
(记录当前这个数出现的次数),最大的众数maxc
(表示树中最大的众数)
思路:
- 按照中序遍历,遍历整个二叉树,在遍历过程中记录
pre
、count
、maxc
。 - 比较当前节点的值与
pre
是否相同,如果相同,则count 加 1
,如果不同,则要比较与maxc
的大小关系 - 如果
count > maxc
说明出现了新的众数,则清空原来的结果数据res
,将新的众数添加进去 - 如果
count == maxc
说明又多了一个众数,将该数加入结果数据, - 最后返回结果数据
递归代码:
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
//首先 对于二叉搜索树,中序遍历是有序的,因此相当于在一个有序的数组上找出众数
var res []int
var pre,maxc,count int
func findMode(root *TreeNode) []int {
maxc = 0
count = 0
res = []int{}
dfs(root)
return res
}
func dfs( root *TreeNode){
if root == nil {
return
}
// 中序遍历
dfs(root.Left)
// 如果是第一个节点,或者当前节点与上一个节点相同,
if count == 0 || root.Val == pre{
count++ //当前众数++
pre = root.Val
}else{ //如果是一个新的数
pre = root.Val
count = 1
}
if count > maxc{
maxc = count
res = []int{root.Val} //更新结果数组,注意直接将之前的结果数组里面的数据全部删除
}else if count == maxc{ //如果当前众数与最大众数相同,则放入结果数组
res = append(res,pre)
}
dfs(root.Right)
}
标签:count,pre,res,树中,众数,maxc,root,LeetCode
From: https://www.cnblogs.com/lxing-go/p/17524333.html