用栈实现二叉树的遍历

用栈实现二叉树的遍历不如用递归实现的简单，需要一些技巧。
用递归实现三种遍历方式只需改变递归顺序就可以依次完成前序、中序、后序的遍历了。
水平有限，如有错误望指正

栈实现前序遍历

栈实现前序遍历较简单，由于每次先输出根节点，再输出左节点随后是右节点。因此我的处理逻辑是：

1、若栈非空输出根节点，并出栈
2、将右节点压栈（如果存在）
3、将左节点压栈（如果存在）
4、重复第1步直到栈空

注意：之所以先压右节点是考虑了栈的特性，这样在迭代过程中可以先拿到左节点处理

以下是代码：

void preTraversal(TreeNode* root){
    if(root==NULL)return;
    TreeNode*cur=root;
    stack<TreeNode*>S;
    S.push(cur);
    while(!S.empty()){
        cur = S.top();
        cout<<cur->val<<" ";
        S.pop();
        if(cur->right!=NULL)S.push(cur->right);
        if(cur->left!=NULL)S.push(cur->left);
    }
    cout<<endl;
}

栈的中序遍历

栈的中序遍历需要套两层循环，由于需要先输出左节点，因此必须向下查找直到左节点为空才能输出。处理逻辑如下：

1、如果栈顶元素非空且左节点存在，将其入栈，重复该过程。若不存在则进入第2步
2、若栈非空，输出栈顶元素并出栈。判断刚出栈的元素的右节点是否存在，不存在重复第2步，存在则将右节点入栈，跳至第1步

代码如下：

void inorderTraversal(TreeNode *root){
    if(root==NULL)return;
    stack<TreeNode *>S;
    S.push(root);
    while(!S.empty()){
        //该过程一直找到没有左节点的节点才停止
        while(S.top()->left!=NULL){
            S.push(S.top()->left);
        }
        //此时的S.top()是一个没有left的节点，按照中序遍历的特性，可以将其直接输出。
        //while循环会一直将栈顶输出，直到遇到有右节点的节点，这样能保证栈中元素不会重复寻找左孩子
        while(!S.empty()){
            TreeNode *cur = S.top();
            cout<<cur>val<<" ";
            S.pop();
            
            if(cur>right!=NULL){
                S.push(cur->right);
                break;
            }
        }
    }
    cout<<endl;
}

栈的后序遍历

后序遍历在中序的双层循环的基础上需要加入一个记录，专门记录上一次出栈的节点。步骤如下：

1、如果栈顶元素非空且左节点存在，将其入栈，重复该过程。若不存在则进入第2步（该过程和中序遍历一致）
2、判断上一次出栈节点是否当前节点的右节点，或者当前节点是否存在右节点，满足任一条件，将当前节点输出，并出栈。否则将右节点压栈。跳至第1步

void postTraversal(TreeNode* root){
    if(root==NULL)return;
    stack<TreeNode*>S;
    S.push(root);
    TreeNode* lastPopNode=NULL;
    while(!S.empty()){
        while(S.top()->left!=NULL){
            S.push(S.top()->left);
        }
        while(!S.empty()){
            if(lastPopNode==S.top()->right||S.top()->right==NULL){
                cout<<S.top()->val<<" ";
                lastPopNode=S.top();
                S.pop();
            }
            else if(S.top()->right!=NULL){
                S.push(S.top()->right);
                break;
            }
        }
    }
    cout<<endl;
}