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
后序遍历为
...
单链表之和
@陈利人在微博上发布了很多有意思的题目，建议大家关注下。
题目地址在这里。
两个单链表（singly linked list），每一个节点里面一个0-9的数字， 输入就相当于两个大数了。然后返回这两个数的和（一个新list）。这两个输入的list 长度相等。 要求是：1. 不用递归。2. 要求算法在最好的情况下，只遍历两个list一次， 最差的情况下两遍。
解答：
第一遍遍历两个链表相加并且存储，第二遍遍历处理节点data >= 10的情况。
如果节点值>10,需要向前进位,需要两个指针，第一个不断迭代链表称为迭代指针，第二个记录需要进位到的节点称为位置指针，此时考虑两种情况：
前一个节点值<9,则前一个节点值+1即可
前一个节点...
228 post articles, 29 pages.