501. 二叉搜索树中的众数

leecode原题

题目

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

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

假定 BST 满足如下定义：

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

示例

示例 1:

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

示例 2:

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

提示：

• 树中节点的数目在范围 [1, 104] 内
• 105 <= Node.val <= 105

进阶:

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

解题思路

思路

如果不考虑不使用额外的空间，不做的优化的话，那本身随便用一个遍历方式，遍历完树，得到所有的元素值，然后可以使用map统计所有值出现的频率，然后排序即可解决。

但是要考虑不使用额外空间的话，那么我们就需要在一次中序遍历中(二叉搜索树在中序遍历中是有序的!!!!)，完成这个操作，可以记录一个Pre指针指向上一个节点，然后每次遍历用当前指针跟上一个指针的值进行比较, 记录即可。

实现

源码

func findMode(root *TreeNode) []int {
    var (
        res      = make([]int, 0)
        maxCount = 0 // 最大统计数
        count    = 0
        pre      *TreeNode
        travel   func(root *TreeNode)
    )
    travel = func(root *TreeNode) {
        // 二叉搜索树通过中序遍历能得到有序数组
        if root == nil {
            return
        }
        // 遍历左子树
        travel(root.Left)
        // 处理根节点
        if pre == nil { // 第一个节点
            count = 1
        } else if root.Val == pre.Val { // 与前一个节点数值相同
            count += 1
        } else {
            count = 1 // 与前一个节点数值不同
        }
        pre = root             // 更新上一个节点
        if count == maxCount { // 要考虑一下存在相同的情况, 比如有两个值，一个1，一个2， 这个时候应该返回[1, 2]
            res = append(res, root.Val)
        }
        if count > maxCount { //大于记录的最大值, 这个时候res数组需要重置
            maxCount = count
            res = make([]int, 0) //!!!!数组重置
            res = append(res, root.Val)
        }
        // 遍历右子树
        travel(root.Right)
    }
    travel(root)
    return res
}