如何在没有额外内存的情况下在O(n)时间内遍历二叉树

给定一个带有整数,左右指针的二叉树,如何在O(n)时间和O(1)额外内存(没有堆栈/队列/递归)中遍历树？

这个人给出了一个解决方案,该解决方案不是将当前路径编码为整数的O(n)总时间(因此适用于有限深度的树).

我正在寻找经典的解决方案

(SPOILER)

编码子节点中每个节点的父节点.

任何好的算法书都会有这个算法,例如在Knuth(TAOCP I.2.3.1 Traversing binary trees,excercise 21)中.但是,因为此算法会修改树,所以在多线程环境中必须格外小心.

您也可以使用线程树(参见Knuth).