blob: 7bba4353e1a758f286e23bcfeea5cd286e750dc8 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include "leetcode.h"
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
// morris traversal
vector<int> nodes;
while (root) {
if (root->left) {
TreeNode *pre = root->left;
while (pre->right && pre->right != root)
pre = pre->right;
if (!pre->right) {
pre->right = root;
nodes.push_back(root->val);
root = root->left;
} else {
pre->right = NULL;
root = root->right;
}
} else {
nodes.push_back(root->val);
root = root->right;
}
}
return nodes;
}
};
|