二叉搜索树的众数（递归，迭代）Java_二叉搜索树中的众数 java

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

假定 BST 有如下定义：

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

 暴力递归法：

/**
 * 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 {
    public int[] findMode(TreeNode root) {
        Map<Integer,Integer> map=new HashMap<>();
        List<Integer> list=new ArrayList<>();
        if(root==null) return list.stream().mapToInt(Integer::intValue).toArray();
        searchBST(root,map);
        List<Map.Entry<Integer,Integer>> 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<mapList.size();i++){
            if(mapList.get(i).getValue()==mapList.get(i-1).getValue()){
                list.add(mapList.get(i).getKey());
            }else{
                break;
            }
        }
        return list.stream().mapToInt(Integer::intValue).toArray();        
    }
    void searchBST(TreeNode node,Map<Integer,Integer> map){
        if(node==null) return;
        map.put(node.val,map.getOrDefault(node.val,0)+1);
        searchBST(node.left,map);
        searchBST(node.right,map);
    }
}

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

/**
 * 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 {
    ArrayList<Integer> 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;i<resList.size();i++){
            res[i]=resList.get(i);
        }
        return res;
        
    }
    public void find(TreeNode root){
        if(root==null) return;
        find(root.left);
        int rootValue=root.val;
        if(pre==null||rootValue!=pre.val){
            count=1;
        }else{
            count++;
        }
        if(count>maxCount){
            resList.clear();
            resList.add(rootValue);
            maxCount=count;
        
        }else if(count==maxCount) resList.add(rootValue);
        pre=root;
        find(root.right);
    }
}

迭代：

/**
 * 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 {
  
    public int[] findMode(TreeNode root) {
       Stack<TreeNode> stack=new Stack<>();
       TreeNode cur=root;
       TreeNode pre=null;
       int maxCount=0;
       int count=0;
       List<Integer> 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();
        
    }
}