算法之二叉搜索树的众数

206 字

1 分钟

算法之二叉搜索树的众数

2021-06-20

算法与基础

二叉树

二叉搜索树

算法

面试题

JavaScript

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

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

假定 BST 有如下定义：

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

解法：

1.递归中序遍历（开辟新空间）

思路：

1
var findMode = function(root) {
2
    let base = 0, count = 0, maxCount = 0;
3
    let answer = [];
4

5
    const update = (x) => {
6
        if (x === base) {
7
            ++count;
8
        } else {
9
            count = 1;
10
            base = x;
11
        }
12
        if (count === maxCount) {
13
            answer.push(base);
14
        }
15
        if (count > maxCount) {
16
            maxCount = count;
17
            answer = [base];
18
        }
19
    }
20

21
    const dfs = (o) => {
22
        if (!o) {
23
            return;
24
        }
25
        dfs(o.left);
26
        update(o.val);
27
        dfs(o.right);
28
    }
29

30
    dfs(root);
31
    return answer;
32
};