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