【力扣-二叉树】18、二叉树中的众数 501 二叉搜索树中

发表于

「这是我参与11月更文挑战的第20天，活动详情查看：2021最后一次更文挑战」

501. 二叉搜索树中的众数

题目描述

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

假定 BST 有如下定义：

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

例如：

给定 BST [1,null,2,2],

1
2
3
4
5
markdown复制代码   1
    \
     2
    /
   2

返回[2].

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

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

解析（针对二叉搜索树）

中序遍历

  • 在中序遍历的过程中，求出众数
  • 二叉搜索树中，左子树节点与根节点值相同，或者右子树节点值与根节点值相同
  • 使用指针pre记录遍历的前一个节点，当pre==NULL时表示遍历的第一个节点，此时pre为空
  • 使用int maxCount记录众数，使用int count记录每个值出现的次数
  • 使用vector<int> result记录众数
  • 在遍历的过程中更新maxCount
  • 只要出现count大于maxCount，就把result数组清空，将当前节点值加入到结果集result

daima

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
57
58
59
60
61
62
63
64
c++复制代码// 中序遍历
class Solution
{
public:
    vector<int> findMode(TreeNode *root)
    {
        result.clear();
        searchBST(root);
        return result;
    }

private:
    // 记录最大值
    int maxCount = 0;
    // 记录每个元素出现的次数
    int count = 0;
    // 结果集
    vector<int> result;
    // 指向前一个节点的指针
    TreeNode *pre = NULL;
    // 中序遍历
    void searchBST(TreeNode *node)
    {
        if (node == NULL)
        {
            return;
        }
        // 左
        searchBST(node->left);
        
        // 遍历的第一个节点
        if (pre == NULL)
        {
            count = 1;
        }
        else if (pre->val == node->val) // 当前一个节点值与当前节点值相同
        {
            count++;
        }
        else // 第一次出现的节点值，计数置为1
        {
            count = 1;
        }
        pre = node;

        // 若计数大于计数的最大值，更新最大值
        // 并且清空之前记录的节点值
        if (count > maxCount)
        {
            result.clear();
            // 更新最大值
            maxCount = count;
            // 重新记录新的节点值
            result.push_back(node->val);
        }
        else if (count == maxCount)
        {
            // 出现的众数可能不止一个
            result.push_back(node->val);
        }
        // 右
        searchBST(node->right);
    }
};

解析（针对普通二叉树）

  • 对于普通的二叉树，节点值得分布没有规律
  • 遍历二叉树
  • 使用map记录每个节点值出现的次数
  • 对 map 进行排序
  • 将出现次数最多的节点值存入结果集

代码

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
c++复制代码// 针对普通二叉树
// 内存会溢出（leetcode上）
class Solution
{
public:
    vector<int> findMode(TreeNode *root)
    {
        vector<int> result;
        // 前序遍历
        traversal(root);
        // 将map转为vector,vector中存储的仍然是pair
        vector<pair<int, int>> tmp(mp.begin(), mp.end());
        // 对 vector进行排序
        sort(tmp.begin(), tmp.end(), compare);

        // 将排序后的vector中的第一个pair的 first 元素加入到 结果集中
        result.push_back(tmp[0].first);
        // 遍历剩余的元素
        for (int i = 0; i < tmp.size(); i++)
        {
            // 过滤掉相同的元素
            if (tmp[i].second == tmp[0].second && tmp[i].first != tmp[0].first)
            {
                result.push_back(tmp[i].first);
            }
        }

        return result;
    }

private:
    map<int, int> mp; // 统计每个节点值出现的次数
    void traversal(TreeNode *node)
    {
        if (node == NULL)
        {
            return;
        }
        // 节点出现次数+1
        mp[node->val]++;
        // 左
        traversal(node->left);
        // 右
        traversal(node->right);
    }
    // 比较pair<int,int>类型的数据，返回第二个值较大的 pair
    bool static compare(const pair<int, int> &a, const pair<int, int> &b)
    {
        return a.second >= b.second;
    }
};
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
c++复制代码
// 修改后
class Solution {
private:

void searchBST(TreeNode* cur, unordered_map<int, int>& map) { // 前序遍历
    if (cur == NULL) return ;
    map[cur->val]++; // 统计元素频率
    searchBST(cur->left, map);
    searchBST(cur->right, map);
    return ;
}
bool static cmp (const pair<int, int>& a, const pair<int, int>& b) {
    return a.second > b.second;
}
public:
    vector<int> findMode(TreeNode* root) {
        unordered_map<int, int> map; // key:元素，value:出现频率
        vector<int> result;
        if (root == NULL) return result;
        searchBST(root, map);
        vector<pair<int, int>> vec(map.begin(), map.end());
        sort(vec.begin(), vec.end(), cmp); // 给频率排个序
        result.push_back(vec[0].first);
        for (int i = 1; i < vec.size(); i++) {
            // 取最高的放到result数组中
            if (vec[i].second == vec[0].second) result.push_back(vec[i].first);
            else break;
        }
        return result;
    }
};

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%