【Leetcode】 501. 二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

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

---

提示：

树中节点的数目在范围 [1, 104] 内

• 105 <= Node.val <= 105

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

AC:

/*
 * @lc app=leetcode.cn id=501 lang=cpp
 *
 * [501] 二叉搜索树中的众数
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * 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 {
public:
    TreeNode* pre = NULL;
    int count = 0;
    int maxCount = 0;
    vector<int> result;
    void traversal(TreeNode* cur) {
        if(cur == NULL)
            return ;
        traversal(cur->left);
        if(pre == NULL)
            count = 1;
        else if(pre->val == cur->val)
        {
            count++;
        }
        else count = 1;
        pre = cur;
        if(count == maxCount)
        {
            result.push_back(cur->val);
        }
        if(count > maxCount)
        {
            maxCount = count;
            result.clear();
            result.push_back(cur->val);
        }
        traversal(cur->right);
        return ;
    }
    vector<int> findMode(TreeNode* root) {
        traversal(root);
        return result;
    }
};
// @lc code=end
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

Tips：

• 对于一次遍历完搜索二叉树，将众数结果统计出来：

		if(count == maxCount)
        {
            result.push_back(cur->val);
        }
        if(count > maxCount)
        {
            maxCount = count;
            result.clear();
            result.push_back(cur->val);
        }
1
2
3
4
5
6
7
8
9
10

The first if statement checks if the count of the current value is equal to the maximum count seen so far (count == maxCount). If the count is equal to the maximum count, then the current value is also a mode of the binary search tree, so the value is added to the result vector using the push_back function.

The second if statement checks if the count of the current value is greater than the maximum count seen so far (count > maxCount). If the count is greater than the maximum count, then the current value is a new mode of the binary search tree, so the result vector is cleared using the clear function, and the current value is added to the result vector using the push_back function. Additionally, the maxCount variable is updated to reflect the new maximum count.

Overall, this block of code is a simple and efficient way to update the result vector with the mode(s) of a binary search tree. The code uses a straightforward approach to keep track of the count of each value in the binary search tree, and updates the result vector whenever a new mode is found. One possible way to improve the code would be to add error checking to ensure that cur is not a null pointer before accessing its value. Additionally, the variable names could be more descriptive to make the code easier to read and understand.

---

• 二叉树双指针的移动：

		pre = cur;
1

The line of code pre = cur; is used to update the pre pointer to point to the current node cur. This is because the function is traversing the binary search tree in order, and pre needs to point to the previous node in order to calculate the count of each value in the binary search tree.

Specifically, the function uses an in-order traversal of the binary search tree to visit each node in ascending order. For each node, the function calculates the count of the node’s value by comparing it to the value of the previous node. If the value is the same as the previous node’s value, then the count is incremented. Otherwise, the count is reset to 1.

The pre pointer is used to keep track of the previous node visited during the in-order traversal. Initially, pre is set to nullptr to indicate that there is no previous node. For each node cur, the line of code pre = cur; updates pre to point to cur, so that pre will point to the previous node during the next iteration of the loop.

Overall, this line of code is a simple and efficient way to update the pre pointer during an in-order traversal of a binary search tree. One possible way to improve the code would be to add error checking to ensure that pre and cur are not null pointers before updating pre. Additionally, the variable names could be more descriptive to make the code easier to read and understand.