给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。
如果树中有不止一个众数,可以按 任意顺序 返回。
假定 BST 满足如下定义:
结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/find-mode-in-binary-search-tree
例:
输入:root = [1,null,2,2] 输出:[2]
解析:由题可知,左子树必须小于等于根节点,右子树必须大于等于根节点,如果为众数,必然为相邻节点,若根节点和左儿子相同,那么左儿子的右儿子只能和根节点相同。同理,若根节点和右儿子相同,那么右儿子的左儿子只能和根节点相同。
/*** 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> answer = new ArrayList<Integer>(); // 列表存实时众数int base=0, count=0, maxCount=0; // 当前的判断值,当前值的计数,当前众数的计数public int[] findMode(TreeNode root) {dfs(root); // 遍历搜索树int[] mode = new int[answer.size()]; // 创建答案存储空间for (int i = 0; i< answer.size(); i++){ // 遍历实时答案存储空间mode[i] = answer.get(i); // 将答案提出} return mode; // 返回答案}public void dfs(TreeNode o){ // 搜索函数if (o == null){ // 叶子节点返回return;}dfs(o.left); // 左子树遍历update(o.val); // 更新dfs(o.right); // 右子树遍历}public void update(int x){ // 更新函数if (x == base){ // 与上一个值相等count++; // 计数加1}else{count = 1; // 第一次遇到,计数为1base = x; // 判断值换成当前值}if (count == maxCount){ // 计数等于当前计数最大值answer.add(base); // 添加到结果列表中}if (count > maxCount){ // 计数大于当前计数最大值maxCount = count; // 更新计数最大值answer.clear(); // 清除列表中的过去式众数answer.add(base); // 更新新的众数}}
}