是否有可能遍历在O（1）辅助空间二叉树（W / O使用栈，队列等），或者有这种被证明是不可能的？如果可能的话，怎么能做到呢？

Is it possible to iterate over a binary tree in O(1) auxiliary space (w/o using a stack, queue, etc.), or has this been proven impossible? If it is possible, how can it be done?

编辑：我已经得到有关的答复这是可能的，如果有指向父节点是有趣的，我不知道可以这样做，但是这取决于你如何看待它，这可以是O（ n）的辅助空间。另外，在我的实际使用的情况下，没有指针到父节点。从现在开始，请回答时假定这一点。

The responses I've gotten about this being possible if there are pointers to parent nodes are interesting and I didn't know that this could be done, but depending in how you look at it, that can be O(n) auxiliary space. Furthermore, in my practical use case, there are no pointers to parent nodes. From now on, please assume this when answering.

推荐答案

天哪，我必须实际键入它从克努特。该解决方案是由约瑟夫·M.·莫里斯[天道酬勤。 PROC。快报的 9 （1979年），197-200。据我所知道的，它运行在O（NlogN）的时间。

Geez, I'll have to actually type it up from Knuth. This solution is by Joseph M. Morris [Inf. Proc. Letters 9 (1979), 197-200]. As far as I can tell, it runs in O(NlogN) time.

static void VisitInO1Memory (Node root, Action<Node> preorderVisitor) {
  Node parent = root ;
  Node right  = null ;
  Node curr ;
  while (parent != null) {
    curr = parent.left ;
    if (curr != null) {
      // search for thread
      while (curr != right && curr.right != null)
        curr = curr.right ;

      if (curr != right) {
        // insert thread
        assert curr.right == null ;
        curr.right = parent ;
        preorderVisitor (parent) ;
        parent = parent.left ;
        continue ;
      } else
        // remove thread, left subtree of P already traversed
        // this restores the node to original state
        curr.right = null ;
    } else
      preorderVisitor (parent) ;

    right  = parent ;
    parent = parent.right ;
  }
}

class Node
{
  public Node left  ;
  public Node right ;
}