//给你一个含重复值的二叉搜索树（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)