当前位置：首页 > news >正文

【二叉搜索树】【前后指针】Leetcode 501. 二叉搜索树中的众数

news 来源：原创 2024/5/9 17:08:40

【二叉搜索树】【前后指针】Leetcode 501. 二叉搜索树中的众数

- 解法1 中序遍历+双指针
- 解法2 我的复杂方法先中序遍历到数组，之后hashmap遍历判断众数之后转化为数组输出

在这里插入图片描述

---------------🎈🎈题目链接🎈🎈-------------------

解法1 中序遍历+双指针

/*** 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> mylist = new ArrayList<>();TreeNode pre = null;int count = 1;int maxcount = 1;public int[] findMode(TreeNode root) {// 中序递归+双指针pre cur比较helper(root);int[] result = new int[mylist.size()];for(int i = 0; i< mylist.size(); i++){result[i] = mylist.get(i);}return result;}public void helper(TreeNode root){// 中序遍历if(root == null) return;helper(root.left);//左//  // 计数if(pre==null || pre.val!=root.val){  // 初始化count 遇到不相等就置count为1 表示当前1个相同的元素count = 1;}else if(pre!=null && pre.val==root.val){ // 满足前后相等条件count++count ++;}//  // 更新结果集if(count > maxcount){maxcount = count;mylist.clear();mylist.add(root.val);}else if(count == maxcount){mylist.add(root.val);}pre = root;helper(root.right); // 右}
}

解法2 我的复杂方法先中序遍历到数组，之后hashmap遍历判断众数之后转化为数组输出

一些方法汇总：

遍历hashmap的key-value

 for(var keyvalue:myhash.entrySet()){keyvalue.getKey();keyvalue.getValue();}

2.清空arraylist:arr.clear
3.最小值Integer.MIN_VALUE
4.ArrayList转化为int[ ]输出

int[] finalresult = new int[result.size()];for(int i = 0; i < result.size();i++){finalresult[i] = result.get(i);}

代码：：：：：

class Solution {public int[] findMode(TreeNode root) {List<Integer> mylist = new ArrayList<>();helper(root, mylist);// 取出众数HashMap<Integer,Integer> myhash = new HashMap<>();for(int i = 0; i < mylist.size();i++){myhash.put(mylist.get(i),myhash.getOrDefault(mylist.get(i),0)+1);}// 遍历hashint max = Integer.MIN_VALUE;List<Integer> result = new ArrayList<>();for(var keyvalue:myhash.entrySet()){if(keyvalue.getValue() > max){result.clear();result.add(keyvalue.getKey());max = keyvalue.getValue();}else if(keyvalue.getValue() == max){result.add(keyvalue.getKey());}}// 输出数组int[] finalresult = new int[result.size()];for(int i = 0; i < result.size();i++){finalresult[i] = result.get(i);}return finalresult;}public void helper(TreeNode root, List<Integer> mylist){  // 中序遍历的到数组里if(root == null) return ;helper(root.left,mylist);mylist.add(root.val);helper(root.right,mylist);}
}