参考博客
/*
* 二叉树的先序遍历 --- 非递归版与递归版
*/
#include <iostream>
#include <stack>
using namespace std;
struct TreeNode{
int val;
TreeNode* left, *right;
TreeNode(int v = 0) : val(v), left(NULL), right(NULL){}
};
void visit(TreeNode* p){ //访问函数,这里简单只设为是打印
cout << p->val << " ";
}
/*******************************************
* 前序遍历
********************************************/
void BT_PreOrder(TreeNode* root){
if(root == NULL) return;
stack<TreeNode*> S;
S.push(root);
while(!S.empty()){
TreeNode* cur = S.top();
S.pop();
visit(cur); //访问
if(cur->right) S.push(cur->right);
if(cur->left) S.push(cur->left);
}
return;
}
/*******************************************
* 中序遍历
********************************************/
void BT_InOrder(TreeNode *root){
stack<TreeNode* > S;
TreeNode *cur = root;
while(true){
while(cur){
S.push(cur); cur = cur->left;
}
if(S.empty()) break;
cur = S.top();
visit(cur);
S.pop();
cur = cur->right;
}
}
/*******************************************
* 后序遍历
********************************************/
void findFirst(stack<TreeNode*> &S); //找到以栈顶节点为根的子树其第一个应该输出的节点
//即按照自己-右节点-左节点的顺序压栈
void BT_PostOrder(TreeNode* root){
if(root == NULL) return;
stack<TreeNode *> S;
TreeNode *cur = root;
S.push(root);
while(!S.empty()){
if(S.top()->left != cur && S.top()->right != cur){ //当前节点不是栈顶节点的子节点
//这里的当前节点指的是上一个输出的节点
//这种关系表示上一个输出节点是左节点,而栈顶是右节点,因为右节点可能有未输出的子树,因此需要进行FindFirst的操作
findFirst(S);
}
visit(cur = S.top());
S.pop();
}
}
void findFirst(stack<TreeNode*> &S) {
//找到以栈顶节点为根的子树其第一个应该输出的节点
while (TreeNode* x = S.top()) {
if (x->left) { //一句话总结,有左先右再左,无左只压右
if (x->right) S.push(x->right);
S.push(x->left);
}
else {
S.push(x->right);
}
}
S.pop(); //删掉栈顶的空指针
}
//前序遍历的递归定义：先根节点，后左子树，再右子树。
//首先，我们遍历左子树，边遍历边打印，并把根节点存入栈中，以后需借助这些节点进入右子树开启新一轮的循环。
void my_pre(TreeNode* root){
if(root == NULL)
return;
TreeNode* p = root;
stack<TreeNode*> s;
while(p||!s.empty()){
while(p){
visit(p);
s.push(p);
p=p->left;
}
if(!s.empty()){
p = s.top();
s.pop();
p = p->right;
}
}
}
void my_in(TreeNode* root){
if(root == NULL)
return;
TreeNode* p = root;
stack<TreeNode*> s;
while(p||!s.empty()){
//一直遍历到左子树最下边，边遍历边保存根节点到栈中
if(p){
s.push(p);
p=p->left;
}
//当p为空时，说明已经到达左子树最下边，这时需要出栈了
else{
p = s.top();
s.pop();
visit(p);
//进入右子树，开始新的一轮左子树遍历(这是递归的自我实现)
p = p->right;
}
}
}
/*
0
|
+ 2 ----- 6
| +---- 5 ---- 10
| + ---- 9
+ 1 ----- 4 ---- 8
+ ---- 7
+---- 3
*/
int main(){
TreeNode n0(0), n1(1), n2(2), n3(3), n4(4),n5(5), n6(6), n7(7),n8(8), n9(9),n10(10);
n0.left = &n1; n0.right = &n2;
n1.left = &n3; n1.right = &n4;
n2.left = &n5; n2.right = &n6;
n4.left = &n7; n4.right = &n8;
n5.left = &n9; n5.right = &n10;
BT_PreOrder(&n0);
cout << endl;
my_pre(&n0);
cout << endl;
BT_InOrder(&n0);
cout << endl;
my_in(&n0);
cout << endl;
BT_PostOrder(&n0);
cout << endl;
}
二叉树的非递归后续遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
vector<int> result;
TreeNode* p = root;
TreeNode* q = nullptr; //用来保存刚访问过的节点
do{
while(p!=nullptr){ //往左下走到底
s.push(p);
p = p->left;
}
q = nullptr;
while(!s.empty()){
p = s.top();
s.pop();
if(p->right == q){ //p为左孩子或者说是可以访问的父节点（右子树已被访问）
result.push_back(p->val);
q = p; // 保存刚刚访问过的节点
}
else { // 当前节点不能访问，需要第二次进栈
s.push(p);
p = p->right; //先处理右子树
break;
}
}
}while(!s.empty());
return result;
}
};
