# C++ Simple Solution, Concise Code, Morris Traversal

• Recursion
O(n) space
O(n) time

``````class Solution {
void dfs(TreeNode* cur, vector<int>& res, int height) {
if (!cur)
return;
if (height >= res.size())
res.push_back(cur->val);
else
res[height] = max(res[height], cur->val);
dfs(cur->left, res, height + 1);
dfs(cur->right, res, height + 1);
}
public:
vector<int> largestValues(TreeNode* root) {
vector<int> res;
int height = 0;
dfs(root, res, height);
return res;
}
};
``````

Morris Traversal
O(1) space
O(n) time
Morris Traversal
Get Height by Morris Traversal

``````class Solution {
public:
vector<int> largestValues(TreeNode* root) {
vector<int> res;
TreeNode* cur = root, *prev = NULL;
int deep = 0;
while (cur) {
if (cur->left == NULL) {
//
if (deep >= res.size())
res.push_back(cur->val);
else
res[deep] = max(res[deep], cur->val);
cur = cur->right;
deep++;
} else {
prev = cur->left;
int move = 1;
while (prev->right && prev->right != cur) {
prev = prev->right;
move++;
}
if (prev->right == NULL) {
if (deep >= res.size())
res.push_back(cur->val);
prev->right = cur;
cur = cur->left;
deep++;
} else {
// back to parent node, remove connection
prev->right = NULL;
deep -= move + 1;
//
if (deep >= res.size())
res.push_back(cur->val);
else
res[deep] = max(res[deep], cur->val);
cur = cur->right;
deep++;
}
}
}
return res;
}
};
``````

• Ooh, keeping track of the depth like that in Morris traversal is very nice. I'd call it "O(1) extra space", the "O(n) space" doesn't do it justice.

• @StefanPochmann Yeah, I typed `O(n)` by mistake. Thanks for your upvote. :)

• @StefanPochmann @yong-cao-7731 how is this O(1) space when the size of the returned vector is dependent on the height of the tree?

• @Megziflips That's why I said "extra". As in "other than the result, since there's nothing that can be done about that".

Although it's not quite right, since the result vector probably has linear extra capacity and also uses extra linear space when it runs out of capacity for a push_back and allocates new space and moves the old data over. Not sure why I didn't think of that back then. Maybe I was just too delighted with the algorithm.

• @StefanPochmann oh okay. Thanks for the feedback. That's understandable.

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