二叉搜索树中的众数

题目描述

力扣链接🔗

代码分析

暴力法

将树作为一个普通树。

遍历二叉搜索树为一个数组，再将数组进行遍历即可，次数使用hashmap统计频率即可。

1. 这个树都遍历了，用map统计频率
2. 把统计的出来的出现频率（即map中的value）排个序
3. 取前面高频的元素

    /**
         * 暴力法（遍历成数组即可）
         *
         * @param root
         * @return
         */
        public int[] findMode(TreeNode root) {
            traversal(root);
            for (int i = 0; i < res.size(); i++) {
                map.put(res.get(i), map.getOrDefault(res.get(i), 0) + 1);
            }
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                if (entry.getValue() >= max) {
                    max = entry.getValue();
                }
            }
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                if (entry.getValue() == max) {
                    temp.add(entry.getKey());
                }
            }
            int[] ints = new int[temp.size()];
            for (int i = 0; i < temp.size(); i++) {
                ints[i] = temp.get(i);
            }
            return ints;
        }
        int max = Integer.MIN_VALUE;
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        public TreeNode traversal(TreeNode root) {
            if (root == null) {
                return null;
            }
            if (root.left != null) traversal(root.left);
            res.add(root.val);
            if (root.right != null) traversal(root.right);
            return root;
        }

递归法

既然是搜索树，它中序遍历就是有序的。

二叉搜索树的递归时的常用方法就是中序遍历，定义一个前节点和当前节点来处理。

由于二叉搜索树是有顺序的，所以通过前节点和当前节点来判断值是否相等，相等则频率加一，由于众数不止一个，需要定义一个最大频率来记录众数出现的次数，当后面的数都等于最大频率时，也将结果记录进去，但是注意：如果后面有比最大频率更大的数时，需要将出现频率赋值给最大频率，同时需要将记录的结果清空，再重新记录。

    /**
     * 递归法（根据二叉树的性质）
     *
     * @param root
     * @return
     */
    public int[] findMode(TreeNode root) {
        searchBST(root);
        int[] ints = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            ints[i] = res.get(i);
        }
        return ints;
    }
    TreeNode pre;
    int maxCount; // 最大频率
    int count; // 统计频率
    List<Integer> res = new ArrayList<>();
    public TreeNode searchBST(TreeNode root) {
        if (root == null) {
            return null;
        }
        searchBST(root.left);   // 左
        if (pre == null) {
            count = 1;  // 第一个节点
        } else if (pre.val == root.val) {
            count++;    // 当当前节点和上一个节点相同，频率加一
        } else {
            count = 1;  // 此时不相同，重新统计
        }
        pre = root;   // 移动到下一个节点
        if (count == maxCount) {   // 此时频率等于最大频率
            res.add(root.val);
        }
        if (count > maxCount) {
            maxCount = count;
            res.clear();    // 此时最大的频率改变，要清空集合里的所有元素
            res.add(root.val);// 重新赋值
        }
        searchBST(root.right);  //右
        return root;
    }
}

迭代法

迭代法处理逻辑递归法一致，只需要将中序迭代法的模板修改即可。

TreeNode pre;
TreeNode cur;
int maxCount; // 最大频率
int count; // 统计频率
List<Integer> res = new ArrayList<>();
/**
 * 迭代法（中序遍历）
 *
 * @param root
 * @return
 */
public int[] findMode(TreeNode root) {
    Stack<TreeNode> stack = new Stack();
    cur = root;
    pre = null;
    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) {
                res.add(cur.val);
            }
            if (count > maxCount) {
                maxCount = count;
                res.clear();
                res.add(cur.val);
            }
            pre = cur;  // 移动节点
            cur = cur.right;  // 遍历右边
        }
    }
    int[] ints = new int[res.size()];
    for (int i = 0; i < res.size(); i++) {
        ints[i] = res.get(i);
    }
    return ints;
}