題目

給你一個含重復(fù)值的二叉搜索樹（BST）的根節(jié)點?root?，找出并返回 BST 中的所有?眾數(shù)（即，出現(xiàn)頻率最高的元素）。

如果樹中有不止一個眾數(shù)，可以按?任意順序?返回。

假定 BST 滿足如下定義：

• 結(jié)點左子樹中所含節(jié)點的值?小于等于?當(dāng)前節(jié)點的值
• 結(jié)點右子樹中所含節(jié)點的值?大于等于?當(dāng)前節(jié)點的值
• 左子樹和右子樹都是二叉搜索樹

示例 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);//定義一個數(shù)組接收答案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);}
}