501. 二叉搜索树中的众数

501. 二叉搜索树中的众数

501. 二叉搜索树中的众数

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

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

假定 BST 满足如下定义：

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

示例 1：

输入：root = [1,null,2,2]
输出：[2]

示例 2：

输入：root = [0]
输出：[0]

提示：

• 树中节点的数目在范围 [1, 10^4] 内
• -10^5 <= Node.val <= 10^5

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

思路

这道题目呢，递归法我从两个维度来讲。

首先如果不是二叉搜索树的话，应该怎么解题，是二叉搜索树，又应该如何解题，两种方式做一个比较，可以加深大家对二叉树的理解。

递归法

如果不是二叉搜索树

如果不是二叉搜索树，最直观的方法一定是把这个树都遍历了，用map统计频率，把频率排个序，最后取前面高频的元素的集合。

具体步骤如下：

• 这个树都遍历了，用map统计频率
• 至于用前中后序哪种遍历也不重要，因为就是要全遍历一遍，怎么个遍历法都行，层序遍历都没毛病！

这里采用前序遍历，代码如下：

// 前序遍历 map[int]int key:元素，value:出现频率
func dfs(root *TreeNode,m map[int]int) {if root == nil {return}m[root.Val]++dfs(root.Left,m)dfs(root.Right,m)
}

我们无法对map中的Value直接排序，所以要把map转化切片，再进行排序，当然切片里面放的需要时key,value对，因为拿到频率最高的后，还得知道它对应的Key是什么，因此定义一个结构体item保存。

代码如下：

type item struct{Key intValue int
}m := make(map[int]int)
// 遍历二叉树，统计每个数字出现的频率
dfs(root,m)// 将map放到列表中，以便于排序
arr := make([]item,0)
for k,v := range m {pair := item{k,v}arr = append(arr,pair)
}// 排序，频率高的排前面
sort.Slice(arr,func(i,j int)bool {return arr[i].Value > arr[j].Value})

取前面高频的元素
此时切片中已经是存放着按照频率排好序的item，那么把前面高频的元素取出来就可以了。

代码如下：

// 第一个就是众数，但众数可能有多个，所以继续看列表后面是否还有同频率的数字mode := arr[0]res := make([]int,0)res = append(res,mode.Key)for i := 1;i < len(arr);i++ {if arr[i].Value == mode.Value {res = append(res,arr[i].Key)} else {break}}return res

整体Go代码如下：

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func findMode(root *TreeNode) []int {// 先遍历二叉树，统计每个数字出现的次数，而后对出现次数排序，取出众数if root == nil {return nil}m := make(map[int]int)// 遍历二叉树，统计每个数字出现的频率dfs(root,m)// 将map放到列表中，以便于排序arr := make([]item,0)for k,v := range m {pair := item{k,v}arr = append(arr,pair)}// 排序，频率高的排前面sort.Slice(arr,func(i,j int)bool {return arr[i].Value > arr[j].Value})// 第一个就是众数，但众数可能有多个，所以继续看列表后面是否还有同频率的数字mode := arr[0]res := make([]int,0)res = append(res,mode.Key)for i := 1;i < len(arr);i++ {if arr[i].Value == mode.Value {res = append(res,arr[i].Key)} else {break}}return res
}type item struct{Key intValue int
}func dfs(root *TreeNode,m map[int]int) {if root == nil {return}m[root.Val]++dfs(root.Left,m)dfs(root.Right,m)
}

所以如果本题没有说是二叉搜索树的话，那么就按照上面的思路写！

是二叉搜索树

既然是搜索树，它中序遍历就是有序的。

中序遍历代码如下：

func dfs(curTreeNode *TreeNode){if curTreeNode == nil {return }dfs(curTreeNode.Left) // 左(处理节点） // 中dfs(curTreeNode.Right) // 右
}

遍历有序数组的元素出现频率，从头遍历，那么一定是相邻两个元素作比较，然后就把出现频率最高的元素输出就可以了。

关键是在有序数组上的话，好搞，在树上怎么搞呢？

这就考察对树的操作了。

在二叉树：530. 二叉搜索树的最小绝对差中我们就使用了pre指针和cur指针的技巧，这次又用上了。

弄一个指针指向前一个节点，这样每次cur（当前节点）才能和pre（前一个节点）作比较。

而且初始化的时候pre = nil，这样当pre为nil时候，我们就知道这是比较的第一个元素。

代码如下：

// 没有前节点，则当前节点是第一个节点，计数为1if prevTreeNode == nil { curCount = 1} else if curTreeNode.Val == prevTreeNode.Val {curCount++} else { // 和前一个节点不同了curCount = 1}

此时又有问题了，因为要求最大频率的元素集合（注意是集合，不是一个元素，可以有多个众数），如果是数组上大家一般怎么办？

应该是先遍历一遍数组，找出最大频率（maxCount），然后再重新遍历一遍数组把出现频率为maxCount的元素放进集合。（因为众数有多个）

这种方式遍历了两遍数组。

那么我们遍历两遍二叉搜索树，把众数集合算出来也是可以的。

但这里其实只需要遍历一次就可以找到所有的众数。

那么如何只遍历一遍呢？

如果 频率curCount 等于 maxCount（最大频率），当然要把这个元素加入到结果集中（以下代码为res切片），代码如下：

if curCount > maxCount { // 如果和最大值相同，放进res中res = append(res,curTreeNode.Val)
}

是不是感觉这里有问题，res怎么能轻易就把元素放进去了呢，万一，这个maxCount此时还不是真正最大频率呢。

所以下面要做如下操作：

频率curCount 大于 maxCount的时候，不仅要更新maxCount，而且要清空结果集（以下代码为res），因为结果集之前的元素都失效了。

if curCount > maxCount { // 当前数是最新的众数res = make([]int,0) // 清空之前的所有众数，因为那些都不是最终的众数res = append(res,curTreeNode.Val)maxCount = curCount // 更新最新众数频率
}

关键代码都讲完了，Go完整代码如下：（只需要遍历一遍二叉搜索树，就求出了众数的集合）

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func findMode(root *TreeNode) []int {// 中序遍历二叉搜索树的结果就是有序的，想同数字会同时连续出现if root == nil {return nil}var prevTreeNode *TreeNode // 记录前一个节点curTreeNode := root  // 当前遍历的节点var maxCount int // 当前为止众数的最大次数var curCount int // 当前数字出现的次数var res []int // 存放结果// 在函数内定义函数变量，是想用闭包访问外部变量，这样那些变量就不用作为参数传递了var dfs  func(curTreeNode *TreeNode)dfs = func(curTreeNode *TreeNode) {if curTreeNode == nil {return}dfs(curTreeNode.Left) // 左// 中 处理逻辑// 没有前节点，则当前节点是第一个节点，计数为1if prevTreeNode == nil { curCount = 1} else if curTreeNode.Val == prevTreeNode.Val {curCount++} else { // 和前一个节点不同了curCount = 1}// 当前数也是众数if curCount == maxCount {res = append(res,curTreeNode.Val)} else if curCount > maxCount { // 当前数是最新的众数res = make([]int,0) // 清空之前的所有众数，因为那些都不是最终的众数res = append(res,curTreeNode.Val)maxCount = curCount // 更新最新众数频率}prevTreeNode = curTreeNode //更新前一个节点dfs(curTreeNode.Right)// 右}dfs(curTreeNode)return res
}

迭代法

只要把中序遍历转成迭代，中间节点的处理逻辑完全一样。

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func findMode(root *TreeNode) []int {// 中序遍历二叉搜索树的结果就是有序的，想同数字会同时连续出现if root == nil {return nil}var prevTreeNode *TreeNode // 记录前一个节点curTreeNode := root  // 当前遍历的节点var maxCount int // 当前为止众数的最大次数var curCount int // 当前数字出现的次数var res []int // 存放结果stack := make([]*TreeNode,0)for curTreeNode != nil || len(stack) != 0 {if curTreeNode != nil {stack = append(stack,curTreeNode)curTreeNode = curTreeNode.Left // 左} else {curTreeNode = stack[len(stack) - 1]stack = stack[0:len(stack) - 1]// 中 处理逻辑// 没有前节点，则当前节点是第一个节点，计数为1if prevTreeNode == nil { curCount = 1} else if curTreeNode.Val == prevTreeNode.Val {curCount++} else { // 和前一个节点不同了curCount = 1}// 当前数也是众数if curCount == maxCount {res = append(res,curTreeNode.Val)} else if curCount > maxCount { // 当前数是最新的众数res = make([]int,0) // 清空之前的所有众数，因为那些都不是最终的众数res = append(res,curTreeNode.Val)maxCount = curCount // 更新最新众数频率}prevTreeNode = curTreeNode //更新前一个节点curTreeNode = curTreeNode.Right // 右}}return res
}

总结

本题在递归法中，我给出了如果是普通二叉树，应该怎么求众数。

知道了普通二叉树的做法时候，我再进一步给出二叉搜索树又应该怎么求众数，这样鲜明的对比，相信会对二叉树又有更深层次的理解了。

在递归遍历二叉搜索树的过程中，我还介绍了一个统计最高出现频率元素集合的技巧， 要不然就要遍历两次二叉搜索树才能把这个最高出现频率元素的集合求出来。

为什么没有这个技巧一定要遍历两次呢？ 因为要求的是集合，会有多个众数，如果规定只有一个众数，那么就遍历一次稳稳的了。

求二叉搜索树中的众数其实是一道简单题，但大家可以发现我写了这么一大篇幅的文章来讲解，主要是为了尽量从各个角度对本题进剖析，帮助大家更快更深入理解二叉树。

需要强调的是leetcode上的耗时统计是非常不准确的，看个大概就行，一样的代码耗时可以差百分之50以上，所以leetcode的耗时统计别太当回事，知道理论上的效率优劣就行了。