每日一题 501二叉搜素树中的众数（中序遍历）

题目

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

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

假定 BST 满足如下定义：

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

示例 1：

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

示例 2：

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

题解

/*** 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> ans = new ArrayList<>();int cur = 0;int cnt = 0;int maxcnt = 0;public int[] findMode(TreeNode root) {dfs(root);//定义一个数组接收答案int[] res = new int[ans.size()];for(int i = 0; i < ans.size(); i++) {res[i] = ans.get(i);}return res;}private void dfs(TreeNode root) {if (root == null) {return;}dfs(root.left);if (root.val == cur) {cnt++;} else {cur = root.val;cnt = 1;}if (maxcnt == cnt) {ans.add(root.val);} else if (maxcnt < cnt) {//更新最大值ans.clear();ans.add(root.val);maxcnt = cnt;}dfs(root.right);}
}