如何將前中后序的遞歸框架改寫(xiě)成迭代形式

2、往左走到頭之后就開(kāi)始退棧，看看棧頂節(jié)點(diǎn)的右指針，非空的話(huà)就重復(fù)第 1 步。

寫(xiě)成迭代代碼就是這樣：

privateStackstk=newStack<>();

publicListtraverse(TreeNoderoot){
pushLeftBranch(root);

while(!stk.isEmpty()){
TreeNodep=stk.pop();
pushLeftBranch(p.right);
}
}

//左側(cè)樹(shù)枝一擼到底，都放入棧中
privatevoidpushLeftBranch(TreeNodep){
while(p!=null){
stk.push(p);
p=p.left;
}
}

上述代碼雖然已經(jīng)可以模擬出遞歸函數(shù)的運(yùn)行過(guò)程，不過(guò)還沒(méi)有找到遞歸代碼中的前中后序代碼位置，所以需要進(jìn)一步修改。

迭代代碼框架

想在迭代代碼中體現(xiàn)前中后序遍歷，關(guān)鍵點(diǎn)在哪里？

當(dāng)我從棧中拿出一個(gè)節(jié)點(diǎn)p，我應(yīng)該想辦法搞清楚這個(gè)節(jié)點(diǎn)p左右子樹(shù)的遍歷情況。

如果p的左右子樹(shù)都沒(méi)有被遍歷，那么現(xiàn)在對(duì)p進(jìn)行操作就屬于前序遍歷代碼。

如果p的左子樹(shù)被遍歷過(guò)了，而右子樹(shù)沒(méi)有被遍歷過(guò)，那么現(xiàn)在對(duì)p進(jìn)行操作就屬于中序遍歷代碼。

如果p的左右子樹(shù)都被遍歷過(guò)了，那么現(xiàn)在對(duì)p進(jìn)行操作就屬于后序遍歷代碼。

上述邏輯寫(xiě)成偽碼如下：

privateStackstk=newStack<>();

publicListtraverse(TreeNoderoot){
pushLeftBranch(root);

while(!stk.isEmpty()){
TreeNodep=stk.peek();

if(p的左子樹(shù)被遍歷完了){
/*******************/
/**中序遍歷代碼位置**/
/*******************/
//去遍歷p的右子樹(shù)
pushLeftBranch(p.right);
}

if(p的右子樹(shù)被遍歷完了){
/*******************/
/**后序遍歷代碼位置**/
/*******************/
//以p為根的樹(shù)遍歷完了，出棧
stk.pop();
}
}
}

privatevoidpushLeftBranch(TreeNodep){
while(p!=null){
/*******************/
/**前序遍歷代碼位置**/
/*******************/
stk.push(p);
p=p.left;
}
}

有剛才的鋪墊，這段代碼應(yīng)該是不難理解的，關(guān)鍵是如何判斷p的左右子樹(shù)到底被遍歷過(guò)沒(méi)有呢？

其實(shí)很簡(jiǎn)單，我們只需要維護(hù)一個(gè)visited指針，指向「上一次遍歷完成的根節(jié)點(diǎn)」，就可以判斷p的左右子樹(shù)遍歷情況了

下面是迭代遍歷二叉樹(shù)的完整代碼框架：

//模擬函數(shù)調(diào)用棧
privateStackstk=newStack<>();

//左側(cè)樹(shù)枝一擼到底
privatevoidpushLeftBranch(TreeNodep){
while(p!=null){
/*******************/
/**前序遍歷代碼位置**/
/*******************/
stk.push(p);
p=p.left;
}
}

publicListtraverse(TreeNoderoot){
//指向上一次遍歷完的子樹(shù)根節(jié)點(diǎn)
TreeNodevisited=newTreeNode(-1);
//開(kāi)始遍歷整棵樹(shù)
pushLeftBranch(root);

while(!stk.isEmpty()){
TreeNodep=stk.peek();

//p的左子樹(shù)被遍歷完了，且右子樹(shù)沒(méi)有被遍歷過(guò)
if((p.left==null||p.left==visited)
&&p.right!=visited){
/*******************/
/**中序遍歷代碼位置**/
/*******************/
//去遍歷p的右子樹(shù)
pushLeftBranch(p.right);
}
//p的右子樹(shù)被遍歷完了
if(p.right==null||p.right==visited){
/*******************/
/**后序遍歷代碼位置**/
/*******************/
//以p為根的子樹(shù)被遍歷完了，出棧
//visited指針指向p
visited=stk.pop();
}
}
}

代碼中最有技巧性的是這個(gè)visited指針，它記錄最近一次遍歷完的子樹(shù)根節(jié)點(diǎn)（最近一次pop出棧的節(jié)點(diǎn)），我們可以根據(jù)對(duì)比p的左右指針和visited是否相同來(lái)判斷節(jié)點(diǎn)p的左右子樹(shù)是否被遍歷過(guò)，進(jìn)而分離出前中后序的代碼位置。

PS：visited指針初始化指向一個(gè)新 new 出來(lái)的二叉樹(shù)節(jié)點(diǎn)，相當(dāng)于一個(gè)特殊值，目的是避免和輸入二叉樹(shù)中的節(jié)點(diǎn)重復(fù)。

只需把遞歸算法中的前中后序位置的代碼復(fù)制粘貼到上述框架的對(duì)應(yīng)位置，就可以把任意遞歸的二叉樹(shù)算法改寫(xiě)成迭代形式了。

比如，讓你返回二叉樹(shù)后序遍歷的結(jié)果，你就可以這樣寫(xiě)：

privateStackstk=newStack<>();

publicListpostorderTraversal(TreeNoderoot){
//記錄后序遍歷的結(jié)果
Listpostorder=newArrayList<>();
TreeNodevisited=newTreeNode(-1);

pushLeftBranch(root);
while(!stk.isEmpty()){
TreeNodep=stk.peek();

if((p.left==null||p.left==visited)
&&p.right!=visited){
pushLeftBranch(p.right);
}

if(p.right==null||p.right==visited){
//后序遍歷代碼位置
postorder.add(p.val);
visited=stk.pop();
}
}

returnpostorder;
}

privatevoidpushLeftBranch(TreeNodep){
while(p!=null){
stk.push(p);
p=p.left;
}
}

當(dāng)然，任何一個(gè)二叉樹(shù)的算法，如果你想把遞歸改成迭代，都可以套用這個(gè)框架，只要把遞歸的前中后序位置的代碼對(duì)應(yīng)過(guò)來(lái)就行了。

迭代解法到這里就搞定了，不過(guò)我還是想強(qiáng)調(diào)，除了 BFS 層級(jí)遍歷之外，二叉樹(shù)的題目還是用遞歸的方式來(lái)做，因?yàn)檫f歸是最符合二叉樹(shù)結(jié)構(gòu)特點(diǎn)的。

說(shuō)到底，這個(gè)迭代解法就是在用棧模擬遞歸調(diào)用，所以對(duì)照著遞歸解法，應(yīng)該不難理解和記憶。