//给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
//
// 如果树中有不止一个众数，可以按 任意顺序 返回。
//
// 假定 BST 满足如下定义：
//
//
// 结点左子树中所含节点的值 小于等于 当前节点的值
// 结点右子树中所含节点的值 大于等于 当前节点的值
// 左子树和右子树都是二叉搜索树
//
//
//
//
// 示例 1：
//
//
//输入：root = [1,null,2,2]
//输出：[2]
//
//
// 示例 2：
//
//
//输入：root = [0]
//输出：[0]
//
//
//
//
// 提示：
//
//
// 树中节点的数目在范围 [1, 10⁴] 内
// -10⁵ <= Node.val <= 10⁵
//
//
//
//
// 进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
//
// Related Topics 树 深度优先搜索 二叉搜索树 二叉树 👍 717 👎 0
//leetcode submit region begin(Prohibit modification and deletion)
import java.util.ArrayList;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/**
* 记录结果的链表
*/
List<Integer> res = new ArrayList<>();
/**
* 记录单个数的频次
*/
int count = 0;
/**
* 记录历史最高频次
*/
int maxCount = 0;
/**
* 记录当前值
*
* @param root
* @return
*/
int recordValue = Integer.MIN_VALUE;
public int[] findMode(TreeNode root) {
findValue(root);
return res.stream().mapToInt(Integer::intValue).toArray();
}
/**
* 寻找的过程中，若发现比当前最多频次的值大的内容，则替换为频次更高的那个值，替换前清空
* res；若频次等于当前值，则新增一个记录；若频次小于当前值，则不做任何处理就跳过它
*
* @param cur
*/
private void findValue(TreeNode cur) {
if (cur == null) {
return;
}
findValue(cur.left);
//重置计数，每当出现新的值时
if (cur.val != recordValue) {
recordValue = cur.val;
count = 0;
}
count++;
/*
当前值大于历史值，则以当前值的频次，作为最高频次；
当前值等于历史值，则将当前值添加到结果记录中，作为
出现频次最高的数之一
*/
if (count > maxCount) {
res.clear();
res.add(recordValue);
maxCount = count;
} else if (count == maxCount) {
res.add(recordValue);
}
findValue(cur.right);
}
}
//leetcode submit region end(Prohibit modification and deletion)
