LeetCode 501. 二叉搜索树中的众数
原题链接
困难
作者:
大明湖的鱼
,
2021-01-25 22:39:44
,
所有人可见
,
阅读 402
感觉这个题好难想到,尤其是这个pre的引用。等有时间问问同学吧,先mark,没看懂
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
//这里传pre不是传引用就会报错,为什么呢?
void inorder(TreeNode* root,TreeNode*& pre, int &curTimes,int& maxTimes,vector<int>& res){
if(root == nullptr) return ;
inorder(root->left,pre,curTimes,maxTimes,res);
if(pre) curTimes = (root->val == pre->val) ? curTimes+1 : 1;
if(curTimes == maxTimes) res.emplace_back(root->val);
else if(curTimes > maxTimes){
res.clear();
res.emplace_back(root->val);
maxTimes = curTimes;
}
pre = root;
inorder(root->right,pre,curTimes,maxTimes,res);
}
vector<int> findMode(TreeNode* root) {
vector<int> res;
if(!root) return res;
TreeNode* pre = nullptr;
int curTimes = 1,maxTimes = 0;
inorder(root,pre,curTimes,maxTimes,res);
return res;
}
};