LeetCode_71_FindModeInBinarySearchTree

1. question: 二叉搜索树中的众数（简单）

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-mode-in-binary-search-tree

示例 1：

输入：root = [1,null,2,2]
输出：[2]

示例 2：

输入：root = [0]
输出：[0]

提示：

树中节点的数目在范围 [1, 104] 内
-105 <= Node.val <= 105

2. answers

这道题是求众数。首先肯定要考虑二叉搜索树的特性：相邻元素才有可能是相等的。因此中序遍历，比较相邻元素，对相同的元素进行计数。因为题目中规定了，即使元素个数为1，也有可能是众数。所以当元素个数大于等于1的时候，就认为它是众数，保存到结果中。后续如果出现数量比他大的元素，则清空结果，并将其加入到结果中。

依然是先中序遍历，保存遍历序列，进行比较。代码如下所示：

public class Solution_0070 {

    // 中序遍历，保存结果
    public static void midOrder(TreeNode tn, List<Integer> result) {

        if(tn == null) return;

        midOrder(tn.left, result);

        result.add(tn.val);

        midOrder(tn.right, result);
    }

    public static int[] findMode(TreeNode root) {

        List<Integer> result = new ArrayList<>();

        midOrder(root, result);

        List<Integer> finalResult = new ArrayList<>();

        // 遍历结果，找到众数。初始化首元素为众数
        int count = 1;  // 对当前元素计数，初始化为首元素
        int preCount = 1;  // 对前一个众数数量计数，初始化为首元素
        finalResult.add(0);     // 存储众数的下标

        // 从第二个元素开始遍历
        // 注意，经测试，题目要求，是众数，即使个数为1，也有可能是众数
        for (int i = 1; i < result.size(); i++) {

            // 如果和前面的元素相等
            if(result.get(i).equals(result.get(i - 1))) {
                // 计数加1
                count++;
            } else {
                // 当前众数的个数重新计算
                count = 1;
            }

            // 判断是否超过了上一个众数的数量，注意，因为众数可能存在多个，所以当=的时候，就将其结果放到数组中，
            // 后续如果出现了大于的，就将数组清空。
            if(count == preCount) finalResult.add(i);
            else if(count > preCount) {

                // 清空结果，重新找众数
                finalResult.clear();
                finalResult.add(i);

                // 此时，此众数及变为上一个众数，更新preCount
                preCount = count;
            }

        }

        int[] res = new int[finalResult.size()];

        int index = 0;
        for(Integer i: finalResult) {
            res[index++] = result.get(i);
        }

        return res;
    }

    public static void main(String[] args) {
        System.out.println();

        TreeNode tn3 = new TreeNode(2);
        TreeNode tn2 = new TreeNode(2, tn3, null);
        TreeNode tn1 = new TreeNode(1, null, tn2);

        int[] result = findMode(tn1);


//        TreeNode tn2 = new TreeNode(2);
//        TreeNode tn1 = new TreeNode(1, null, tn2);
//
//        int[] result = findMode(tn1);


        for (int value : result) {
            System.out.print(value + "\t");
        }
    }
}

同样，其实在遍历的时候，就可以进行计数了，这里采用成员变量来保存结果。本来想着递归进行引用传递，后来发现计数用到的是基本数据类型，所以采用成员变量的方式来保存结果。代码如下所示：

public class Solution_0070_02 {

    public static List<Integer> result;
    public TreeNode pre;
    public int count;
    public int preCount;

    // 中序遍历，保存结果
    public void midOrder(TreeNode tn) {

        if(tn == null) return;

        midOrder(tn.left);

        // 判断当前元素和上一个元素是否相等
        if(pre != null && tn.val == pre.val) count++;
        else count = 1;

        // 跟新众数
        // 判断是否超过了上一个众数的数量，注意，因为众数可能存在多个，所以当=的时候，就将其结果放到数组中，
        // 后续如果出现了大于的，就将数组清空。
        if(count == preCount) result.add(tn.val);
        else if(count > preCount) {

            // 清空结果，重新找众数
            result.clear();

            result.add(tn.val);

            // 此时，此众数及变为上一个众数，更新preCount
            preCount = count;
        }

        // 更新下次要比较的元素
        pre = tn;

        midOrder(tn.right);
    }

    public int[] findMode(TreeNode root) {
        result = new ArrayList<>();

        // 中序遍历
        midOrder(root);

        // 将结果转换为数组
        int[] res = new int[result.size()];

        int index = 0;
        for(Integer i: result) {
            res[index++] = i;
        }

        return res;
    }

    public static void main(String[] args) {
        System.out.println();

//        TreeNode tn3 = new TreeNode(2);
//        TreeNode tn2 = new TreeNode(2, tn3, null);
//        TreeNode tn1 = new TreeNode(1, null, tn2);
//
        Solution_0070_02 s = new Solution_0070_02();
//
//        int[] result = s.findMode(tn1);


        TreeNode tn2 = new TreeNode(2);
        TreeNode tn1 = new TreeNode(1, null, tn2);

        int[] result = s.findMode(tn1);


        for (int value : result) {
            System.out.print(value + "\t");
        }
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。