501.二叉搜索树中的众数

发表于 | 分类于
字数统计: 439 | 阅读时长 ≈ 1

一、题目描述

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

假定 BST 有如下定义：

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

例如：
给定 BST [1,null,2,2],

1
2
3
4
5
1
 \
  2
 /
2

返回[2].

提示：如果众数超过1个，不需考虑输出顺序

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

二、题解

1.迭代+遍历

1.1 思路

  1. 迭代法获得递增序列
  2. for循环寻找递增序列中的众数

1.2 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#define maxSize 10000
int *findMode(struct TreeNode *root, int *returnSize)
{
    *returnSize = 0;
    if (root == NULL)
        return NULL;
    int arr[maxSize];
    int arrTop = -1;
    struct TreeNode *stack[maxSize], *p = root;
    int stackTop = -1;
    while (stackTop != -1 || p != NULL)
    {
        while (p != NULL)
        {
            stack[++stackTop] = p;
            p = p->left;
        }
        p = stack[stackTop--];
        arr[++arrTop] = p->val;
        p = p->right;
    }
    //在有序数组中找众数
    int *res = (int *)malloc(maxSize * sizeof(int));
    int mode = arr[0]; //当前数字
    int mode_num = 0;  //当前数字的数量
    int nums = 0;      //众数的数量
    for (int i = 0; i <= arrTop; i++)
    {
        if (arr[i] == mode) //如果等于当前数字，
            mode_num++;     //当前数字数量加一
        else
            mode_num = 1;
        if (mode_num > nums) //如果当前数字的数量>众数的数量
        {
            res[0] = arr[i]; //从头开始添加众数
            *returnSize = 1;
            nums = mode_num; //更新众数的数量
        }
        else if (mode_num == nums)
            res[(*returnSize)++] = arr[i];
        mode = arr[i];
    }
    return res;
}