二叉树结构
-前序遍历结果：1-2-4-5-6-7-3-8-9
递归遍历
1
2
3
4
5
| void pre(TreeNode* root,vector<int> &res){
res.push_back(root->val);
pre(root->left,res);
pre(root->right,res);
}
|
迭代（非递归）遍历
思路一:
步骤（思路）：
1. 沿着根的左孩子，依次入栈并访问，直到左孩子为空
2. 栈顶元素出栈：
若其右孩子为空，继续步骤2；
若右孩子不空，将右子树执行步骤1.
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
29
| vector<int> preorderTraversal(TreeNode* root) {
if(!root)
return {};
vector<int> res;
stack<TreeNode*> mystack;
TreeNode* temp=root;
while(temp){
mystack.push(temp);
res.push_back(temp->val);
temp=temp->left;
}
while(mystack.size()){
temp=mystack.top();
mystack.pop();
temp=temp->right;
while(temp){
mystack.push(temp);
res.push_back(temp->val);
temp=temp->left;
}
}
return res;
}
|
思路二：
步骤（思路）：
1. 将根压入栈中；
2. 栈顶元素出栈并访问：
先右后左，将孩子依次压入栈中。
重复步骤一直至栈为空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| vector<int> preorderTraversal(TreeNode* root) {
if(!root)
return {};
vector<int> res;
stack<TreeNode*> mystack;
mystack.push(root);
TreeNode* temp;
while(mystack.size()){
temp=mystack.top();
mystack.pop();
res.push_back(temp->val);
if(temp->right){
mystack.push(temp->right);
}
if(temp->left){
mystack.push(temp->left);
}
}
return res;
}
|
-中序遍历结果：4-2-6-5-7-1-3-9-8
递归遍历
1
2
3
4
5
6
| void mid(TreeNode* root,vector<int> &res){
mid(root->left,res);
res.push_back(root->val);
mid(root->right,res);
}
|
迭代（非递归）遍历
步骤（思路）：
1. 沿着根的左孩子，依次入栈，直到左孩子为空
2. 栈顶元素出栈并访问：
若其右孩子为空，继续步骤2；
若右孩子不空，将右子树执行步骤1.
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
| vector<int> inorderTraversal(TreeNode* root) {
if(!root)
return {};
vector<int> res;
stack<TreeNode*> mystack;
TreeNode* temp=root;
while(temp){
mystack.push(temp);
temp=temp->left;
}
while(mystack.size()){
temp=mystack.top();
mystack.pop();
res.push_back(temp->val);
temp=temp->right;
while(temp){
mystack.push(temp);
temp=temp->left;
}
}
return res;
}
|
注意到：该实现与前序遍历的迭代遍历中思路一高度相似：按照先序序列进栈，出栈的序列一定是一个中序序列(该结论必定正确，帮助记忆前序遍历与中序遍历，但是不需要证明)
-后序遍历结果：4-6-7-5-2-9-8-3-1
递归遍历
1
2
3
4
5
6
| void postorder(TreeNode* root,vector<int> &res){
postorder(root->left,res);
postorder(root->right,res);
res.push_back(root->val);
}
|
迭代(非递归)遍历
步骤（思路）：
1. 沿着根的左孩子，依次入栈，直到左孩子为空
2.扫描栈顶元素：
若无右孩子,弹出并访问,修改辅助指针。
若有右孩子：
右孩子未被访问过，将右孩子视为根节点执行步骤一。
右孩子已被访问过，不再访问右孩子。
利用一个辅助指针记录上一个被访问的结点
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
29
30
31
32
| vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> mystack;
TreeNode *temp, *last;
temp = root;
last = nullptr;
while (temp) {
mystack.push(temp);
temp = temp->left;
}
while (mystack.size()) {
temp = mystack.top();
if (!temp->right) {
mystack.pop();
last = temp;
res.push_back(temp->val);
} else {
if (temp->right == last) {
mystack.pop();
last = temp;
res.push_back(temp->val);
} else {
temp = temp->right;
while (temp) {
mystack.push(temp);
temp = temp->left;
}
}
}
}
return res;
}
|
