501-二叉搜索树中的众数

Doublew2w大约 3 分钟

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

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

假定 BST 满足如下定义：

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

示例 1：

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

示例 2：

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

提示：

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

进阶： 你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

思路

一个二叉搜索树的中序遍历是一个非递减的有序序列。

中序遍历序列是 {−1,0,0,1,2,2}。会发现连续的数字是一小段一小段的出现。

用 prev 来记录当前节点的上一个节点情况，curCount 来表示当前元素的重复次数，``mMaxCount来表示最大的重复次数,mode` 存储众数元素

递归终止条件：当树为空时，直接返回

递归逻辑：

遍历左子树
遍历第一个节点时，curCount = 1 , maxCount =1, 并将该元素放进 mode 中，即默认当前这个是众数
遇到与 prev 相同的节点，更新重复次数，并判断是否是众数
- 如果是众数，就添加进 mode
- 如果不是众数，就说明存在一个元素比 mode 中的任何元素的重复次数还要大。要清空 mode ，并将元素添加进去
遇到与 prev 不相同的节点，更新重复次数，并判断是否是众数
更新 prev 为当前节点
遍历右子树

关键点

二叉树的特性

代码

语言支持：Java

Java Code:


/**
 * 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 {
    List<Integer> mode = new ArrayList<>();
    TreeNode prev = null;
    // 当前元素的重复次数
    int curCount = 0;
    // 全局的最长相同序列长度
    int maxCount = 0;

    public int[] findMode(TreeNode root) {
        // 执行中序遍历
        traverse(root);

        int[] res = new int[mode.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = mode.get(i);
        }
        return res;
    }

    public void traverse(TreeNode root) {
        if (root == null)
            return;
        traverse(root.left);
        if (prev == null) {
            curCount = 1;
            maxCount = 1;
            mode.add(root.val);
        } else {
            // root.val 重复的情况, 判断是否是众数
            if (root.val == prev.val) {
                curCount++;
                if (curCount == maxCount) {
                    // root.val 是众数
                    mode.add(root.val);
                } else if (curCount > maxCount) {
                    mode.clear();
                    maxCount = curCount;
                    mode.add(root.val);
                }
            }
            // root.val 不重复的情况, 重新记录
            if (root.val != prev.val) {
                
                curCount = 1;
                if (curCount == maxCount) {
                    mode.add(root.val);
                }
            }
        }
        // 别忘了更新 prev
        prev = root;

        traverse(root.right);
    }
}

复杂度分析

令 n 为二叉树节点个数。

时间复杂度： $O(n)$ ，即遍历这棵树的复杂度。
空间复杂度： $O(n)$ ，即递归的栈空间的空间代价。

501-二叉搜索树中的众数

题目地址(501. 二叉搜索树中的众数 - 力扣（LeetCode）)

题目描述

思路

关键点

代码