501.二叉搜索树中的众数

一、题目描述

给定一个有相同值的二叉搜索树(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;
}