Home

Morris遍历二叉树

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

Read more