Leetcode501

链接：力扣 。

题目：

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

假定 BST 有如下定义：

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

说明：如果众数超过1个，不需考虑输出顺序 。

示例1：

输入：root = [1,null,2,2]
输出：[2]

示例2：

输入：root = [0]
输出：[0]

思路：

对于本题，如果是一棵普通的树，那么就只能遍历完所有结点，然后用map来统计出现次数。

但是本题为二叉搜索树。对于BST，用中序遍历访问就可以得到一个升序数组。而在一个升序的数组中，相同值的元素一定是连续出现的。这就给我们解题带来了思路。

参考代码：

/**
 * 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:
    int count, maxCount;
    vector<int> result;
    void traversal(TreeNode* root, TreeNode* &pre) {
        if (root == nullptr) {
            return;
        }
        traversal(root->left, pre);
        if (pre == nullptr || pre->val == root->val) {
            count++;
        }
        else {
            count = 1;
        }
        pre = root;
        if (count > maxCount) {
            result.clear();
            result.push_back(root->val);
            maxCount = count;
        }
        else if (count == maxCount) {
            result.push_back(root->val);
        }
        traversal(root->right, pre);
    }
    vector<int> findMode(TreeNode* root) {
        count = 0;
        maxCount = 0;
        TreeNode *pre = nullptr;
        result.clear();
        traversal(root, pre);
        return result;
    }
};