本文轉(zhuǎn)載至： http://zhexue.sinaapp.com/?p=79
已知二叉樹中每個節(jié)點的左右孩子節(jié)點和父節(jié)點，用非遞歸的方式，不能使用任何額外的空間和函數(shù)（自己寫的可以），中序遍歷二叉樹。假設(shè)二叉樹根節(jié)點root的父節(jié)點為NULL。
題目要求不使用任何額外的內(nèi)存空間，這確實夠BT，還好給了每個節(jié)點的父指針，可以好好利用這個信息。思路如下：
（1）如果第一次到達(dá)某個節(jié)點時，如果有左孩子節(jié)點，立即訪問左孩子節(jié)點。
（2）如果節(jié)點沒有左孩子節(jié)點，則訪問右孩子節(jié)點。
（3）從子節(jié)點返回時，如果當(dāng)前節(jié)點的父節(jié)點的右孩子節(jié)點等于當(dāng)前節(jié)點（條件1，這說明該父節(jié)點及其子節(jié)點都已經(jīng)訪問過了），則從當(dāng)前節(jié)點返回到當(dāng)前節(jié)點的父節(jié)點，直到條件1不成立為止。
代碼下載（包括遞歸，基于stack的非遞歸，不用額外空間的非遞歸）