二叉树后序遍历的非递归算法

二叉树后序遍历的非递归算法。很久以前，我曾经问过一位老师，“二叉树后序遍历的非递归算法怎么实现啊？”老师说，“你可以使用栈来实现。”于是，我就开始了解和学习关于二叉树后序遍历的非递归算法了。

二叉树后序遍历，顾名思义，就是先遍历二叉树的左子树，然后遍历右子树，最后才访问根节点。由于这种遍历方式需要先遍历完左右子树，才能遍历根节点，所以我们需要使用一个栈来记录节点，好让我们回到之前遍历时还未遍历完的节点进行处理。因此，我们需要一个参数来标识当前是否为第一次访问该节点，以及栈来存储中间节点。

具体做法如下：

1.对于任意节点，如果左节点不为空，则将该节点压入栈，并将左节点作为当前节点，重复步骤1。

2.当左子树为空时，先判断右子树是否也为空，如果右子树不为空，则将这个节点的标记改为已访问，并将当前节点设置为右子节点，重复步骤1。

3.如果左右子树均为空或已被访问过，则访问该节点并出栈，将当前节点设置为NULL。

4.重复步骤1到3，直到栈为空。

这就是二叉树后序遍历的非递归算法。下面是详细代码：

```

voidpostOrderTraversal(TreeNode*root){

stack<TreeNode*>nodeStack;

TreeNode*current=root;

TreeNode*lastVisited=nullptr;

while(!nodeStack.empty()||current!=nullptr){

if(current!=nullptr){

nodeStack.push(current);

current=current->left;

}else{

TreeNode*peekNode=nodeStack.top();

if(peekNode->right!=nullptr&&lastVisited!=peekNode->right){

current=peekNode->right;

}else{

cout<<peekNode->val<<"";

lastVisited=peekNode;

nodeStack.pop();

}

}

}

}

```

首先，我们先创建一个空的栈和一个指向根节点的指针current。在遍历过程中，我们需要记录上一次被访问的节点，初始值为nullptr。

我们将current不断的压入栈中，并将current设置为它的左孩子节点，直到current走到二叉树最左边的节点。当current为空时，我们从栈中取出栈顶元素，判断它是否有右子树，并且上一个被访问的节点不是其右子树。如果上一个被访问的节点不是其右子树，说明右子树尚未被遍历。因此，我们应该将current指向其右孩子节点，以此来完成对右子树的遍历。否则，说明右子树已经遍历完成，我们访问当前栈顶元素并将其出栈。然后，我们将lastVisited设置为栈顶元素，以标记它已经被访问过。最后，将current设置为nullptr，让之后从栈中取出的节点不再对其进行左子树遍历。

在这个非递归算法中，我们使用了lastVisited来判断右子树是否已经被遍历。这样能够省去另外一个栈。如果不使用lastVisited变量