创建子文件夹new文章：hexo new post -p ./LeetCode学习/Tree前中后序遍历.md
前序遍历
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;
if(root == nullptr) return res;
stack<TreeNode*> stk;
TreeNode* node = root;
while(!stk.empty() || node != nullptr){
while(node != nullptr){
res.push_back(node->val);
stk.push(node);
node = node->left;
}
node = stk.top();
stk.pop();
node = node->right;
}
return res;
}
};
|
中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> sta;
while(root!=nullptr || !sta.empty()){
while(root != nullptr){
sta.push(root);
root = root->left;
}
root = sta.top();
sta.pop();
res.push_back(root->val);
root = root->right;
}
return res;
}
};
|
后序遍历
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
| class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
TreeNode* node = root;
TreeNode* pre = nullptr;
while(!stk.empty()|| node!=nullptr){
while(node !=nullptr){
stk.push(node);
node= node->left;
}
node = stk.top();
stk.pop();
if(node->right==nullptr || pre == node->right){
res.push_back(node->val);
pre=node;
node=nullptr;
}
else{
stk.push(node);
node = node->right;
}
}
return res;
}
};
|