给定一个二叉树的根节点 root ，返回它的 前序 遍历。
颜色标记法
算法思想在中序遍历那篇 。
算法实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<pair<TreeNode *, int>> s;
s.push(make_pair(root, 0));
while (!s.empty()) {
pair<TreeNode *, int> node = s.top();
s.pop();
if(node.first == nullptr) {
continue;
}
if(!node.second) {
s.push(make_pair(node.first->right, 0));
s.push(make_pair(node.first->left, 0));
s.push(make_pair(node.first, 1));
} else {
res.push_back(node.first->val);
}
}
return res;
}
};
|
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
void preOrder(TreeNode * node, vector<int>& res) {
if(node == nullptr) {
return;
}
res.emplace_back(node->val);
preOrder(node->left, res);
preOrder(node->right, res);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
preOrder(root, res);
return res;
}
};
|
非递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode *> s;
TreeNode * p = root;
while (p || !s.empty()) {
while (p) {
res.emplace_back(p->val);
s.push(p);
p = p->left;
}
p = s.top();
s.pop();
p = p->right;
}
return res;
}
};
|