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
后序遍历为
...
238 post articles, 30 pages.