本文转载至： http://zhexue.sinaapp.com/?p=79
已知二叉树中每个节点的左右孩子节点和父节点，用非递归的方式，不能使用任何额外的空间和函数（自己写的可以），中序遍历二叉树。假设二叉树根节点root的父节点为NULL。
题目要求不使用任何额外的内存空间，这确实够BT，还好给了每个节点的父指针，可以好好利用这个信息。思路如下：
（1）如果第一次到达某个节点时，如果有左孩子节点，立即访问左孩子节点。
（2）如果节点没有左孩子节点，则访问右孩子节点。
（3）从子节点返回时，如果当前节点的父节点的右孩子节点等于当前节点（条件1，这说明该父节点及其子节点都已经访问过了），则从当前节点返回到当前节点的父节点，直到条件1不成立为止。
代码下载（包括递归，基于stack的非递归，不用额外空间的非递归）