二叉樹后序遍歷的非遞歸算法

二叉樹后序遍歷的非遞歸算法。很久以前，我曾經(jīng)問過一位老師，“二叉樹后序遍歷的非遞歸算法怎么實(shí)現(xiàn)??？”老師說，“你可以使用棧來實(shí)現(xiàn)?！庇谑?，我就開始了解和學(xué)習(xí)關(guān)于二叉樹后序遍歷的非遞歸算法了。

二叉樹后序遍歷，顧名思義，就是先遍歷二叉樹的左子樹，然后遍歷右子樹，最后才訪問根節(jié)點(diǎn)。由于這種遍歷方式需要先遍歷完左右子樹，才能遍歷根節(jié)點(diǎn)，所以我們需要使用一個(gè)棧來記錄節(jié)點(diǎn)，好讓我們回到之前遍歷時(shí)還未遍歷完的節(jié)點(diǎn)進(jìn)行處理。因此，我們需要一個(gè)參數(shù)來標(biāo)識當(dāng)前是否為第一次訪問該節(jié)點(diǎn)，以及棧來存儲中間節(jié)點(diǎn)。

具體做法如下：

1.對于任意節(jié)點(diǎn)，如果左節(jié)點(diǎn)不為空，則將該節(jié)點(diǎn)壓入棧，并將左節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，重復(fù)步驟1。

2.當(dāng)左子樹為空時(shí)，先判斷右子樹是否也為空，如果右子樹不為空，則將這個(gè)節(jié)點(diǎn)的標(biāo)記改為已訪問，并將當(dāng)前節(jié)點(diǎn)設(shè)置為右子節(jié)點(diǎn)，重復(fù)步驟1。

3.如果左右子樹均為空或已被訪問過，則訪問該節(jié)點(diǎn)并出棧，將當(dāng)前節(jié)點(diǎn)設(shè)置為NULL。

4.重復(fù)步驟1到3，直到棧為空。

這就是二叉樹后序遍歷的非遞歸算法。下面是詳細(xì)代碼：

```

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();

}

}

}

}

```

首先，我們先創(chuàng)建一個(gè)空的棧和一個(gè)指向根節(jié)點(diǎn)的指針current。在遍歷過程中，我們需要記錄上一次被訪問的節(jié)點(diǎn)，初始值為nullptr。

我們將current不斷的壓入棧中，并將current設(shè)置為它的左孩子節(jié)點(diǎn)，直到current走到二叉樹最左邊的節(jié)點(diǎn)。當(dāng)current為空時(shí)，我們從棧中取出棧頂元素，判斷它是否有右子樹，并且上一個(gè)被訪問的節(jié)點(diǎn)不是其右子樹。如果上一個(gè)被訪問的節(jié)點(diǎn)不是其右子樹，說明右子樹尚未被遍歷。因此，我們應(yīng)該將current指向其右孩子節(jié)點(diǎn)，以此來完成對右子樹的遍歷。否則，說明右子樹已經(jīng)遍歷完成，我們訪問當(dāng)前棧頂元素并將其出棧。然后，我們將lastVisited設(shè)置為棧頂元素，以標(biāo)記它已經(jīng)被訪問過。最后，將current設(shè)置為nullptr，讓之后從棧中取出的節(jié)點(diǎn)不再對其進(jìn)行左子樹遍歷。

在這個(gè)非遞歸算法中，我們使用了lastVisited來判斷右子樹是否已經(jīng)被遍歷。這樣能夠省去另外一個(gè)棧。如果不使用lastVisited變量