Morris遍历二叉树
Morris遍历不使用栈，O(1)空间进行二叉树的遍历。
原理就是：
利用叶子结点的右空指针，临时性的指向中序遍历的后继结点。
与这篇文章的想法类似，前序和中序非常相近，顺序是相同的，不同的是访问的时机。
1. 前序、中序遍历
#pseudo code
while 结点存在:
if 左子树存在:
找到左子树的最右结点，
如果发现左子树的最右结点:#这个最右结点也就是当前结点在中序遍历下的前驱结点
该结点右指针指向当前结点
否则如果最右结点的右指针已经指向当前结点:
还原最右结点的右指针指向NULL
else:
访问该结点
转到右...
由两种遍历结果构造二叉树
还是二叉树遍历的题目，不过是由遍历结果反推二叉树。
Construct Binary Tree from Preorder and Inorder Traversal
Construct Binary Tree from Inorder and Postorder Traversal
两个题目是类似的，关于树的问题第一反映就是递归。以中序、后序推导为例，
中序结果为LNR,后序结果为LRN,因此可以通过后序结果的最后一个node(即根节点)，在中序结果中查找，就可以区分L,R，然后继续递归计算即可。
举个列子，假设二叉树为
1
/ \
2 3
/ \
4 5
中序遍历为
4 2 5 1 3
后序遍历为
...
158 post articles, 20 pages.