按级别顺序打印二叉树,每个节点仅使用一个额外指针

Question

给定一个二叉树,其节点具有以下类型:

struct Node {
  Node* left;
  Node* right;
  int data;
  Node* foo;   // uninitialized - use it any way you like
};

按级别顺序打印树数据,并使foo每个节点的成员指向下一个兄弟节点.

除了具有非数组类型的常量变量外,我们不允许使用任何其他存储(特别是不允许使用外部队列).

Answer 1

这个想法非常简单 - 队列可以表示为链表,因此用于foo指示链表中的下一个节点,并且只跟踪最后一个节点以进行排队.

伪代码:

current = root
lastNode = current
while current != null
   process current
   if current.left != null
      if lastNode != null
         lastNode.foo = current.left
      lastNode = lastNode.foo
   if current.right != null
      if lastNode != null
         lastNode.foo = current.right
      lastNode = lastNode.foo
   current = current.foo

为了简单起见,我假设所有foo的都被初始化为null.
如果不是这种情况,只需在lastNode.foo = null每次lastNode更改时设置.

如果我们想要foo任何给定级别中的最后一个节点null而不是指向下一级别的第一个节点(这可能是需求的一部分 - 它有点不清楚),我们可以相当容易地跟踪第一个节点下一级,并设置current.foo为null指向该节点的时间.

正确性的关键在于树中永远不会有多个级别,因此firstNextLevel不能跳过级别,并且只有在我们处于级别的开始时才会设置.

current = root
lastNode = current
firstNextLevel = null

while current != null
   process current

   if current.left != null
      if lastNode != null
         lastNode.foo = current.left
      lastNode = lastNode.foo
      if firstNextLevel == null
         firstNextLevel = lastNode

   if current.right != null
      if lastNode != null
         lastNode.foo = current.right
      lastNode = lastNode.foo
      if firstNextLevel == null
         firstNextLevel = lastNode

   if current.foo == firstNextLevel
      temp = current
      current = current.foo
      temp.foo = null
      firstNextLevel = null
   else
      current = current.foo

然后是一个绝望的过于复杂的解决方案,只涉及foo指向同一级别的下一个节点.

我们只需要foo在遍历此级别时设置下一级别,并跟踪下一级别的第一个节点,以便我们知道从完成此级别后的位置.

伪代码看起来像:

current = root
firstInNextLevel = null
prevInNextLevel = null
while current != null
   // this loop can happen twice for current, so we need this check
   if prevInNextLevel != current.left
      process current

   // pick left first, then right, then nothing
   if current.left != null && prevInNextLevel != current.left
                           && prevInNextLevel != current.right
      currentInNextLevel = current.left
   else if current.right != null && prevInNextLevel != current.right
      currentInNextLevel = current.right
   else
      currentInNextLevel = null

   if currentInNextLevel != null
      // set up foo for previous node
      if prevInNextLevel != null
         prevInNextLevel.foo = currentInNextLevel
      else
         firstInNextLevel = currentInNextLevel
      prevInNextLevel = currentInNextLevel
   else
      // done with current, move on
      current = current.foo
      // no nodes left on this level, move on to the next
      if current == null
         if prevInNextLevel != null
            prevInNextLevel.foo = null
         current = firstInNextLevel
         firstInNextLevel = null
         prevInNextLevel = null