向内螺旋树遍历

Question

我遇到了一个有趣的问题:

给定二进制树以向内螺旋顺序打印它,即第一打印级别1,然后是级别n,然后是级别2,然后是n-1,依此类推.

For Ex:
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15

Should Output:
1 15 14 13 12 11 10 9 8 2 3 7 6 5 4

我想到了一个解决方案:

• 将每个级别元素存储在列表
  列表中[0] = [1]
  列表[1] = [2,3]
  列表[2] = [4,5,6,7]
  列表[3] = [8,9,10 ,11,12,13,14,15]

• 按所需顺序(0,n-1,1,n-2,...)循环列表列表并打印.以下n是在上述情况下为4的级别数.

它的空间复杂度为O(n).我相信可能有一个更好的解决方案,它有更好的空间复杂性,但我想不出它.任何人有任何指针？

Answer 1

这是一个关于O(1)空间和O(n * h)时间的简单解决方案，其中n是节点数，h是树高。保留两个指向当前级别的变量进行打印，然后根据长度对应于适当的树深度的二进制字符串打印遍历树后的每个节点；向左移动“0”，向右移动“1”（例如，示例中最左边的节点是“000”，它的邻居是“001”）。由于要打印一个节点，我们最多必须制作h迭代，时间复杂度为O(n * h)。

这是稍微更详细的算法：

down = 0
up = tree height

while:
  if down > up:
    break
  else:
    set exp to down then up (or only one if up == down):
      for i = 0 to 2^exp - 1:
        s = binary string i, padded to exp digits
        traverse tree according to s
        if a node exists by the end of s:
          print node
    down = down + 1
    up = up - 1

我不确定它是否会快一个数量级，但是您可以使用相同的原理在树中行走，而不是从每个节点的根开始：返回直到遇到“0”，翻转它到“1”，然后一直向左一直向下到目标级别并递归重复，直到字符串全为“1”。例如，目标级别 4：

0000 => (000)1 => (00)10 => (001)1 => (0)100...etc.