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;
}
};
```