501. 二叉搜索樹中的眾數(shù)
空間復(fù)雜度遍歷二叉樹（沒有開棧空間），因?yàn)槊總€(gè)節(jié)點(diǎn)訪問次數(shù)不超過2方面，因此時(shí)間復(fù)雜度是
class Solution {
public:
int cntm, cur, cnt;
vector<int> vec;
void update(int x) {
if (vec.empty()) {
cur = x, cnt = 1, cntm = max(cnt, cntm), vec.push_back(cur);
} else {
if (x != cur) cur = x, cnt = 1;
else cnt++;
if (cnt > cntm) cntm = cnt, vec = vector<int>{cur};
else if (cnt == cntm) vec.push_back(cur);
}
}
vector<int> findMode(TreeNode *root) {
TreeNode *cur = root;
TreeNode *pre = nullptr;
while (cur) {
if (!cur->left) {
update(cur->val), cur = cur->right;
continue;
}
pre = cur->left;
while (pre->right && pre->right != cur) {
pre = pre->right;
}
if (!pre->right)pre->right = cur, cur = cur->left;
else pre->right = nullptr, update(cur->val), cur = cur->right;
}
return vec;
}
};
