【算法与数据结构】501、LeetCode二叉搜索树中的众数

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

二、解法

  思路分析：根据前面几篇文章98、LeetCode验证二叉搜索树、530、LeetCode二叉搜索树的最小绝对差。我们知道二叉搜索树中序遍历时有序数组，那么程序当中去使用pre和cur指针，去判断两个节点键值是否相同，相同则频率++，不同则count记为1，然后判断count是否等于maxcount，如果相等说明是众数，加入结果数组，如果小于，则更新maxcount，并且要清空结果数组（结果数组里面可能有之前maxcount的对应元素），在将更新后的众数加入结果数组，最后不断递归。
  程序如下：

class Solution {
private:
    int maxCount = 0; // 最大频率
    int count = 0; // 统计频率
    TreeNode* pre = NULL;
    vector<int> result;
    void searchBST(TreeNode* cur) {
        if (cur == NULL) return;

        searchBST(cur->left);       // 左
        // 中
        if (pre == NULL) { // 第一个节点
            count = 1;
        }
        else if (pre->val == cur->val) { // 与前一个节点数值相同
            count++;
        }
        else { // 与前一个节点数值不同
            count = 1;
        }
        pre = cur; // 更新上一个节点

        if (count == maxCount) { // 如果和最大值相同，放进result中
            result.push_back(cur->val);
        }

        if (count > maxCount) { // 如果计数大于最大值频率
            maxCount = count;   // 更新最大频率
            result.clear();     // 很关键的一步，不要忘记清空result，之前result里的元素都失效了
            result.push_back(cur->val);
        }

        searchBST(cur->right);      // 右
        return;
    }

public:
    vector<int> findMode(TreeNode* root) {
        count = 0;
        maxCount = 0;
        TreeNode* pre = NULL; // 记录前一个节点
        result.clear();

        searchBST(root);
        return result;
    }
};
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

三、完整代码

# include 
# include 
# include 
# include 
using namespace std;

// 树节点定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
private:
    int maxCount = 0; // 最大频率
    int count = 0; // 统计频率
    TreeNode* pre = NULL;
    vector<int> result;
    void searchBST(TreeNode* cur) {
        if (cur == NULL) return;

        searchBST(cur->left);       // 左
        // 中
        if (pre == NULL) { // 第一个节点
            count = 1;
        }
        else if (pre->val == cur->val) { // 与前一个节点数值相同
            count++;
        }
        else { // 与前一个节点数值不同
            count = 1;
        }
        pre = cur; // 更新上一个节点

        if (count == maxCount) { // 如果和最大值相同，放进result中
            result.push_back(cur->val);
        }

        if (count > maxCount) { // 如果计数大于最大值频率
            maxCount = count;   // 更新最大频率
            result.clear();     // 很关键的一步，不要忘记清空result，之前result里的元素都失效了
            result.push_back(cur->val);
        }

        searchBST(cur->right);      // 右
        return;
    }

public:
    vector<int> findMode(TreeNode* root) {
        count = 0;
        maxCount = 0;
        TreeNode* pre = NULL; // 记录前一个节点
        result.clear();

        searchBST(root);
        return result;
    }
};

// 前序遍历迭代法创建二叉树，每次迭代将容器首元素弹出（弹出代码还可以再优化）
void Tree_Generator(vector<string>& t, TreeNode*& node) {
    if (!t.size() || t[0] == "NULL") return;    // 退出条件
    else {
        node = new TreeNode(stoi(t[0].c_str()));    // 中
        if (t.size()) {
            t.assign(t.begin() + 1, t.end());
            Tree_Generator(t, node->left);              // 左
        }
        if (t.size()) {
            t.assign(t.begin() + 1, t.end());
            Tree_Generator(t, node->right);             // 右
        }
    }
}

template<typename T>
void my_print(T& v, const string msg)
{
    cout << msg << endl;
    for (class T::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << ' ';
    }
    cout << endl;
}

template<class T1, class T2>
void my_print2(T1& v, const string str) {
    cout << str << endl;
    for (class T1::iterator vit = v.begin(); vit < v.end(); ++vit) {
        for (class T2::iterator it = (*vit).begin(); it < (*vit).end(); ++it) {
            cout << *it << ' ';
        }
        cout << endl;
    }
}

// 层序遍历
vector<vector<int>> levelOrder(TreeNode* root) {
    queue<TreeNode*> que;
    if (root != NULL) que.push(root);
    vector<vector<int>> result;
    while (!que.empty()) {
        int size = que.size();  // size必须固定, que.size()是不断变化的
        vector<int> vec;
        for (int i = 0; i < size; ++i) {
            TreeNode* node = que.front();
            que.pop();
            vec.push_back(node->val);
            if (node->left) que.push(node->left);
            if (node->right) que.push(node->right);
        }
        result.push_back(vec);
    }
    return result;
}

int main()
{
    vector<string> t = { "1", "NULL", "2", "2", "NULL", "NULL", "NULL" };   // 前序遍历
    my_print(t, "目标树");
    TreeNode* root = new TreeNode();
    Tree_Generator(t, root);
    vector<vector<int>> tree = levelOrder(root);
    my_print2<vector<vector<int>>, vector<int>>(tree, "目标树:");

    Solution s;
    vector<int> result = s.findMode(root);
    my_print(result, "众数：");

    system("pause");
    return 0;
}
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

end