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