501. 二叉搜索树中的众数

501. 二叉搜索树中的众数

思路

二叉搜索树的中序遍历是一个升序序列，逐个比对当前结点(root)值与前驱结点（pre)值。更新当前节点值出现次数(curTimes)及最大出现次数(maxTimes)，更新规则：若curTimes=maxTimes,将root->val添加到结果向量(res)中；若curTimes>maxTimes,清空res,将root->val添加到res,并更新maxTimes为curTimes。

代码

class Solution {
public:
    void inorder(TreeNode* root, int& currTimes, int& maxTimes,vector<int>& result,TreeNode*& pre){
        if(root == NULL){
            return;
        }
        inorder(root->left,currTimes,maxTimes,result,pre);
        if(pre){
            currTimes = (root->val == pre->val) ? currTimes+1:1;
        }
        if(currTimes == maxTimes){
            result.push_back(root->val);
        }
        if(currTimes > maxTimes){
            result.clear();
            result.push_back(root->val);
            maxTimes = currTimes;
        }
        pre = root;
        inorder(root->right,currTimes,maxTimes,result,pre);
    }
    vector<int> findMode(TreeNode* root) {
        vector<int> result;
        if(root == NULL){
            return result;
        }
        int currTimes = 1,maxTimes = 0;
        TreeNode* pre = NULL;
        inorder(root,currTimes,maxTimes,result,pre);
        return result;
    }
};