【LeetCode】二叉搜索树中的众数

题目描述：

https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/

解题熟路1:(首先我是用额外的空间）

因二叉搜索树中序遍历呈现的顺序是从小到大的，故先中序遍历二叉树，存入数组，再判断众数

代码1:

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        vector<int> res;
        vector<int> res1;
        if(!root)
            return res;
        if(!root->left && !root->right)
        {
            res.push_back(root->val);
            return res;
        }
        int currTimes=1, maxTimes=0;
        pre(root, res1);
        int i=1;
        for(; i<res1.size(); i++)
        {
            if(res1[i] == res1[i-1])
                currTimes++;
            else if(currTimes == maxTimes)
            {
                res.push_back(res1[i-1]);
                currTimes=1;
            }
            else if(currTimes > maxTimes)
            {
                res.erase(res.begin(), res.end());
                res.push_back(res1[i-1]);
                maxTimes = currTimes;
                currTimes=1;
            }
            else
                currTimes = 1;
        }
        if(currTimes == maxTimes)
            res.push_back(res1[i-1]);
        else if(currTimes>maxTimes)
        {
            res.clear();
            res.push_back(res1[i-1]);
        }
        return res;
    }
    void pre(TreeNode *root, vector<int>& res1)
    {
        if(!root)
            return;
        else
        {
            pre(root->left, res1);
            res1.push_back(root->val);
            pre(root->right, res1);
        }
    }
};

代码2:不用额外的空间

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