无论是二叉树的中序遍历还是用 stack 模拟递归， 都需要 O(n)的空间复杂度。

　　Morris 遍历是一种 常数空间 的遍历方法，其本质是 线索二叉树(Threaded Binary Tree), 本质上其实就是利用二叉树中 n+1 个指向NULL的指针。

　　Morris 遍历在遍历的过程中，通过利用叶子节点空的right指针，指向中序遍历的下一个节点，从而避免了对 stack 的依赖。

　　// Morris Traversal

　　// space effienct

　　void InOrderVisitMorris(TreeNode *root)

　　{

　　TreeNode *pre(NULL);

　　while(root)

　　{

　　// 左子树是空，直接访问该节点，然后访问右子树

　　if(root->left_child == NULL){

　　cout << root->value << " ";

　　root = root->right_child;

　　continue;

　　}

　　// 找 root 的前驱节点

　　for(pre = root->left_child; pre->right_child && pre->right_child != root; pre = pre->right_child);

　　// 第一次访问root, 建立线索

　　if(pre->right_child == NULL){

　　pre->right_child = root;

　　root = root->left_child;

　　}

　　// 第二次访问，说明左子树已经访问过

　　else{

　　pre->right_child = NULL;

　　cout << root->value << " ";

　　root = root->right_child;

　　}

　　}

　　}