Morris遍历二叉树
Morris遍历不使用栈,O(1)空间进行二叉树的遍历。
原理就是:
利用叶子结点的右空指针,临时性的指向中序遍历的后继结点。
与这篇文章的想法类似,前序和中序非常相近,顺序是相同的,不同的是访问的时机。
1. 前序、中序遍历
#pseudo code
while 结点存在:
if 左子树存在:
找到左子树的最右结点,
如果发现左子树的最右结点:#这个最右结点也就是当前结点在中序遍历下的前驱结点
该结点右指针指向当前结点
否则如果最右结点的右指针已经指向当前结点:
还原最右结点的右指针指向NULL
else:
访问该结点
转到右...
207 post articles, 26 pages.