做装修效果图的网站,南阳做网站优化的公司,上海保洁服务网站建设,佛山seo优化评价题目链接#xff1a;501. 二叉搜索树中的众数 - 力扣#xff08;LeetCode#xff09;
题目描述#xff1a; 思路分析#xff1a;
由题可知#xff0c;题目中所给的树是一颗二叉搜索树#xff0c;二叉搜索树的中序遍历结果是一个从小到大的数据集#xff0c;那么我们可…题目链接501. 二叉搜索树中的众数 - 力扣LeetCode
题目描述 思路分析
由题可知题目中所给的树是一颗二叉搜索树二叉搜索树的中序遍历结果是一个从小到大的数据集那么我们可以根据这一特性来获取到二叉搜索树中的所有 val放在一个 List 中并且这个 List 是有序的。获取到二叉搜索树中的所有 val 之后我们接下来就可以寻找众数。我们使用 max 来记录 List 中众数出现的次数使用 Map 来保存 val 及其出现的次数这样在后面我们就可以直接从 Map 中获取到 val 出现的次数。如果 val 出现的次数等于 max那么这个数就是一个众数我们再使用一个 ArrayList 来存放众数将所有的众数都存放到 ArrayList 之后我们再将 ArraryList 中的数据拷贝到数组中就可以了。
代码示例
class Solution {public int[] findMode(TreeNode root) {ListInteger list new LinkedList();// 中序遍历inOrder(root,list);// 存放众数MapInteger,Integer map new HashMap();int max 1;for(int i 0; i list.size(); i) {int tmp list.get(i);int j i;while(i list.size() list.get(i) tmp) {i;}Integer cnt i-j;map.put(tmp,cnt);max cnt max ? cnt : max;i--;}// ans 存放最终结果ArrayListInteger ans new ArrayList();for(int i 0; i list.size(); i) {if(map.size() 0) break; if(map.get(list.get(i)) null) continue;if(map.get(list.get(i)) max) {ans.add(list.get(i));map.remove(list.get(i));}}// 将 ans 的数据拷贝回数组中int[] res new int[ans.size()];int i 0;for(int x : ans) {res[i] x;}return res;}public void inOrder(TreeNode root,ListInteger list) {if(root null) return;inOrder(root.left,list);list.add(root.val);inOrder(root.right,list);}
}
