LeetCode 501. 二叉搜索树中的众数

Categories:

题目描述
思路分析
1. 解法一：中序遍历统计频次（推荐）
相似题目

题目描述

✅ 501. 二叉搜索树中的众数

思路分析

解法一：中序遍历统计频次（推荐）

核心思路：

BST 的中序遍历是有序序列，相同值会连续出现。

遍历时维护当前值的计数 count、最大计数 maxCount，并更新结果集合。

通过 prev 记录上一个值，判断是否延续计数。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数。

空间复杂度：O(h)，其中 h 表示树高，递归栈使用。

import java.util.ArrayList;
import java.util.List;

class Solution {
    private Integer prev = null;
    private int count = 0;
    private int maxCount = 0;
    private final List<Integer> modes = new ArrayList<>();

    public int[] findMode(TreeNode root) {
        inorder(root);

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

    private void inorder(TreeNode node) {
        if (node == null) {
            return;
        }

        inorder(node.left);

        // 统计当前值的连续次数
        if (prev == null || node.val != prev) {
            count = 1;
            prev = node.val;
        } else {
            count++;
        }

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

        inorder(node.right);
    }
}

func findMode(root *TreeNode) []int {
	hasPrev := false
	prevVal := 0
	count := 0
	maxCount := 0
	modes := make([]int, 0)

	var inorder func(node *TreeNode)
	inorder = func(node *TreeNode) {
		if node == nil {
			return
		}

		inorder(node.Left)

		if !hasPrev || node.Val != prevVal {
			count = 1
			prevVal = node.Val
			hasPrev = true
		} else {
			count++
		}

		if count > maxCount {
			maxCount = count
			modes = modes[:0]
			modes = append(modes, node.Val)
		} else if count == maxCount {
			modes = append(modes, node.Val)
		}

		inorder(node.Right)
	}

	inorder(root)
	return modes
}

相似题目

题目	难度	考察点
98. 验证二叉搜索树	中等	BST
230. 二叉搜索树中第K小的元素	中等	BST 中序
235. 二叉搜索树的最近公共祖先	简单	BST 性质
530. 二叉搜索树的最小绝对差	简单	BST 中序
700. 二叉搜索树中的搜索	简单	BST 查找

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/43919770