二叉搜索树的众数（递归，迭代）Java

二叉搜索树的众数（递归，迭代）Java

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

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

 暴力递归法：

class Solution {
    public int[] findMode(TreeNode root) {
        Map map=new HashMap<>();
        List list=new ArrayList<>();
        if(root==null) return list.stream().mapToInt(Integer::intValue).toArray();
        searchBST(root,map);
        List> mapList=map.entrySet().stream().sorted((c1,c2)->c2.getValue().compareTo(c1.getValue())).collect(Collectors.toList());

        list.add(mapList.get(0).getKey());

        for(int i=1;i map){
        if(node==null) return;
        map.put(node.val,map.getOrDefault(node.val,0)+1);
        searchBST(node.left,map);
        searchBST(node.right,map);
    }
}

优化递归：利用二叉搜索树的特点。

class Solution {
    ArrayList resList;
    int maxCount;
    int count;
    TreeNode pre;
    public int[] findMode(TreeNode root) {
        resList=new ArrayList<>();
        maxCount=0;
        count=0;
        pre=null;
        find(root);
        int []res=new int[resList.size()];
        for(int i=0;imaxCount){
            resList.clear();
            resList.add(rootValue);
            maxCount=count;
        
        }else if(count==maxCount) resList.add(rootValue);
        pre=root;
        find(root.right);
    }
}

迭代：

class Solution {
  
    public int[] findMode(TreeNode root) {
       Stack stack=new Stack<>();
       TreeNode cur=root;
       TreeNode pre=null;
       int maxCount=0;
       int count=0;
       List list=new ArrayList<>();
       while(cur!=null||!stack.isEmpty()){
          if(cur!=null){
              stack.push(cur);
              cur=cur.left;
          }else{
             cur=stack.pop();
             if(pre==null) count=1;
             else if(pre.val==cur.val) count++;
             else count=1;
             if(count==maxCount) list.add(cur.val);
            
            if(count>maxCount){
            maxCount=count;
            list.clear();
            list.add(cur.val);
            
        
        }
        pre=cur;
        cur=cur.right;
          }
          }


        return list.stream().mapToInt(Integer::intValue).toArray();
        
    }
}