# C++ 0(1) space solution with detail explanation and comment, can anyone make it faster?

• The first one consumes lot of space. Nothing to comment.

``````class Solution_extra_memory_version {
public:
vector<int> findMode(TreeNode* root) {
vector<int> res;
if (!root) return res;
unordered_map<int, int> mp;
int maxV = INT_MIN;
dfs(root, mp, maxV);
for (auto c: mp) if (c.second == maxV) res.push_back(c.first);
return res;
}

void dfs(TreeNode* root, unordered_map<int, int> &mp, int &maxV) {
if (!root) return;
mp[root->val]++;
maxV = max(maxV, mp[root->val]);
dfs(root->left, mp, maxV);
dfs(root->right, mp, maxV);
}
};
``````

Here is the second one

/* idea: inorder traverse gives us sorted number

e.g. 1 1 2 2 2 2 3 3

If we can use two pointers to count the occurrence of every number, (if val == last: cnt++; otherwise cnt = 1)
the problem can be solved.

I used a stack<pair<int, int>> to remember the target result

if a new and better set of solutions comes out, pop the old one and push new

one trick here is to memorize the last value when we traverse the tree, I can't find a logic to express it now, instead I used a 2-len deque .

another trick is to consider the corner case, i.e. the last node and the case when there is only one node*/

``````class Solution { // my own o(1) memory solution
void inorder(TreeNode* &root, stack<pair<int, int>> &stk, int &cnt, deque<int> &dq) {
if (!root) return;

inorder(root->left, stk, cnt, dq);
dq.push_back(root->val);
if (dq.size() > 2) dq.pop_front(); // trim deque when its length goes beyong 2

if (dq.front() == root->val) cnt++;
else {
if (dq.front() != INT_MIN && dq.front() != root->val && (stk.empty() || cnt >= stk.top().second)) {
if (!stk.empty() && cnt > stk.top().second) while (!stk.empty()) stk.pop(); // when we meet better solution, clear the old one
stk.push(pair<int, int>(dq.front(), cnt));
}
cnt = 1; // put it outside the above loop
}

inorder(root->right, stk, cnt, dq);
}

public:
vector<int> findMode(TreeNode* root) {
int cnt = 1;
vector<int> res;
if (root && !root->left && !root->right) { // corner case: handle one-node example
res.push_back(root->val);
return res;
}

stack<pair<int, int>> stk;
deque<int> dq;

dq.push_back(INT_MIN); // insert a fake number, there should be better ways to handle this part. It has potentially bug
inorder(root, stk, cnt, dq);

if (dq.front() != INT_MIN  && (stk.empty() || cnt >= stk.top().second)) { // corner case: handle the last node
if (!stk.empty() && cnt > stk.top().second) while (!stk.empty()) stk.pop();
stk.push(pair<int, int>(dq.back(), cnt));
}

while (!stk.empty()) { // change result format
res.push_back(stk.top().first);
stk.pop();
}
return res;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.