binary-tree - 通过修改 morris 遍历实现 PreOrder 和 PostOrder 遍历

Question

morris 遍历非常适用于 O(n) 时间和 O(1) 空间的 InOrder 遍历。是否有可能仅通过更改一些东西来使用相同的算法实现 PreOrder 和 PostOrder 遍历。

Answer 1

我不认为我们可以使用线程实现后序。
在后序中，我们必须遍历两个 child ，然后是他们的 parent 。
我们可以建立一个从 child 到 parent 的链接，但之后我们不能去这个 parent ，因为他们没有链接。(一个指向左 child ，一个指向它的右 child 没有向上)

             1
            / \
           2   3
          / \
         4   5

我们可以在 4 的右节点创建一个指向节点 5 的线程。
我们可以在 5 的右节点创建一个指向节点 2 的线程。

但是在节点 2 没有空指针来创建任何线程。节点 2 已经有指向节点 4 和 5 的指针。