501.二叉搜索树中的众数

1、概要

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

如果不是二叉搜索树

如果不是二叉搜索树，最直观的方法一定是把这个树都遍历了，用map统计频率，把频率排个序，最后取前面高频的元素的集合。

是二叉搜索树

既然是搜索树，它中序遍历就是有序的。遍历有序数组的元素出现频率，从头遍历，那么一定是相邻两个元素作比较，然后就把出现频率最高的元素输出就可以了。

2、思路

递归

考察对树的操作了。弄一个指针指向前一个节点，这样每次cur（当前节点）才能和pre（前一个节点）作比较。

而且初始化的时候pre = NULL，这样当pre为NULL时候，我们就知道这是比较的第一个元素。

if(pre == null){
    count = 1;
}else if(pre.val == cur.val){
    count ++;
}else{
    count = 1;
}
pre = cur;

//if(pre == null || pre.val != cur.val){
	//count = 1;
//}else{count++；}

那么如何只遍历一遍呢？

如果频率count 等于 maxCount（最大频率），当然要把这个元素加入到结果集中

// 如果和最大值相同，放进result中
if(count == maxCount){
    result.add(cur.val);
}

频率count 大于 maxCount的时候，不仅要更新maxCount，而且要清空结果集，因为结果集之前的元素都失效了。

 // 如果计数大于最大值 更新最大频率
if(count > maxCount){
    maxCount = count;
    // 很关键的一步，不要忘记清空result，之前result里的元素都失效了
    result.clear;
    result.add(cur.val);
}

只需要遍历一遍二叉搜索树，就求出了众数的集合

迭代

只要把中序遍历转成迭代，中间节点的处理逻辑完全一样。

3、代码

class Solution {
    LinkedList<Integer> resList = new LinkedList<>();
    Stack<TreeNode> stack = new Stack<>();
    int maxCount = 0;//最大频率
    int count = 0;//统计频率
    TreeNode pre = null;
    public int[] findMode(TreeNode root) {
        //reCurSion(root);
        iteRaTion(root);
        int[] res = new int[resList.size()];
        for (int i = 0; i < resList.size(); i++) {
            res[i] = resList.get(i);
        }
        return res;
    }
    public void iteRaTion(TreeNode node){
        if(node == null){
            return;
        }
        stack.push(node);
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            if(cur!=null){
                if(cur.right !=null){
                    stack.push(cur.right);
                }
                stack.push(cur);
                stack.push(null);
                if(cur.left!=null){
                    stack.push(cur.left);
                }
            }else{
                cur = stack.pop();
                // 第一个节点或与前一个节点数值不同，频率不变保持1
                if(pre == null || cur.val != pre.val){
                    count = 1;
                }else{
                    count++;
                }

                pre = cur;
                
                if(count > maxCount){// 如果计数大于最大值频率
                    maxCount = count;// 更新最大频率
                    resList.clear();// 很关键的一步，不要忘记清空result，之前result里的元素都失效了
                    resList.add(cur.val);
                }else if(count == maxCount){// 如果和最大值相同，放进result中
                    resList.add(cur.val);
                }
            }
        }

    }
    public void reCurSion(TreeNode node){
        if(node == null){
            return;
        }
        reCurSion(node.left);

        if(pre == null ||  node.val != pre.val){
            count = 1;
        }else{
            count++;
        }

        if(count > maxCount ){
            resList.clear();
            resList.add(node.val);
            maxCount = count;
        }else if(count == maxCount){
            resList.add(node.val);
        }

        pre = node;

        reCurSion(node.right);
    }
}

JZTXT

25.二叉搜索树中的众数