501_find_mode_in_binary_search_tree

501. 二叉搜索树中的众数 简单

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

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

例如：
给定 BST [1,null,2,2],

   1
    \
     2
    /
   2

返回[2].

提示：如果众数超过1个，不需考虑输出顺序

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

代码参考：

package main

import "fmt"

func main() {
    root := &TreeNode{Val: 1}
    root.Right = &TreeNode{Val: 2}
    root.Right.Left = &TreeNode{Val: 2}

    //    1
    //    \
    //     2
    //    /
    //   2
    fmt.Println(findMode(root)) // 2
}

// 辣鸡解法是将二叉树随便遍历到计数 map 后，两次遍历求众数即可
// cool solution // 理解本质
func findMode(root *TreeNode) []int {
    var res []int
    var cur, count, max int
    traverseBST(root, &cur, &count, &max, &res)
    return res
}

// 既然是 BST，那就中序遍历取出有序序列，一边遍历一边比较并取众数
func traverseBST(root *TreeNode, cur, count, max *int, res *[]int) {
    if root == nil {
        return
    }
    traverseBST(root.Left, cur, count, max, res)

    if root.Val != *cur {
        *cur = root.Val // 新值
        *count = 1
    } else {
        *count++
    }

    // 新众数纪录
    if *count > *max {
        *max = *count
        *res = nil // 重来
    }

    // 符合众数条件
    if *count == *max {
        *res = append(*res, root.Val)
    }
    traverseBST(root.Right, cur, count, max, res)
}