algorithm - 将二叉树转换为链表，广度优先，常量存储/破坏性

这不是家庭作业，我也不需要回答，但现在我已经迷上了：）
问题是：
设计一个算法，以毁灭性的扁平化二叉树到一个链表，广度优先。好吧，很简单。只需建立一个队列，然后做你必须做的事情。
那是热身赛。现在，用常量存储实现它（递归，如果你能用它找到答案的话，就是对数存储，而不是常量）。
一年前我在网上找到了解决这个问题的方法，但现在我忘记了，我想知道：）
据我所知，诀窍在于利用算法的破坏性，使用树来实现队列。在链接列表时，还将项目推入队列。
每次我试图解决这个问题时，我都会丢失节点（例如每次我链接下一个节点/添加到队列时），我需要额外的存储，或者我无法找出返回到具有所需指针的节点所需的卷积方法。
即使是那篇原创文章/帖子的链接对我也很有用：）谷歌没有给我任何乐趣。
编辑：
Jérémie指出，如果你有一个父指针的话，有一个相当简单的答案（也是众所周知的答案）。虽然我现在认为他对包含父指针的原始解决方案是正确的，但我真的希望在没有父指针的情况下解决问题：）
细化的需求对节点使用此定义：

struct tree_node
{
  int value;
  tree_node* left;
  tree_node* right;
};

最佳答案

想法是：
可以沿着树的左侧子级生成链接列表。同时，该列表的右子级用于保存要在尾部插入的下一个子树的队列。
伪码算法：
（编辑：为清晰起见重写）
节点有三个组件：一个值、对其左子节点的引用和对其右子节点的引用。引用可能为空。
将此类节点的二叉树转换为单个链表的函数
将对根节点的引用作为参数root，
循环，tail从root的左子级开始：
将tail的左子项与root的右子项交换，
循环（o（n）队列插入），bubble-to从root开始，bubble-from始终是bubble-to的左子项，
将bubble-to的右子项与“bubble from”的右子项交换，
向他们的左孩子推进bubble-to和bubble-from，
直到bubble-from达到tail，
向左边的孩子前进，
而tail不为空。
最后，返回tail。现在，单个链接列表将沿着左侧子项运行。
插图
起始树（我认为它应该是一个完整的树；如果节点丢失，它们应该从末尾开始。你可以试着给其他案例赋予意义，但这有几种不同的可能性，其中涉及到很多摆弄）：

              1
          /       \
      2               3
    /   \           /   \
  4       5       6       7
 / \     / \     / \     / \
8   9   A   B   C   D   E   F

请注意，这些值不一定是节点的值，它们只是为了显示目的而编号的。
一次迭代后的树（注意从head到1的列表和根在3和4中的子树队列）：

                head
                  v
                  1
               /    \
    tail    2         4
      v  /    \      / \
      3         5   8   9
    /   \      / \
  6       7   A   B
 / \     / \
C   D   E   F

经过3次迭代（列表现在是5到1，队列保存根在5到6中的子树）：

                   head
                     v
                     1
                  /     \
               2          6
             /   \       / \
           3       7    C   D
          / \     / \
         4   8   E   F
        / \
tail > 5   9
      / \
     A   B

经过8次迭代（几乎完成）：

实数代码（Lisp）
这是节点类：

(defclass node ()
  ((left :accessor left)
   (right :accessor right)
   (value :accessor value)))

一个有用的助手：

(defmacro swap (a b)
  `(psetf ,a ,b
          ,b ,a))

转换功能（编辑：为清晰起见而重写）：

(defun flatten-complete-tree (root)
  (loop for tail = (and root (left root)) then (left tail)
        while tail
        do (swap (left tail) (right root))
           (loop for bubble-to = root then (left bubble-to)
                 for bubble-from = (left bubble-to)
                 until (eq bubble-from tail)
                 do (swap (right bubble-to) (right bubble-from))))
  root)

参差不齐的树木的不可逆操作：
我重写了上面的内容，允许任意参差不齐的树。不过，你再也不能从中重建原来的树了。

(defun flatten-tree (root)

；这里的内部循环将9保留在尚未展开的子树的根上，
；即第一个分支的节点，
同时熨烫从根部到左边的所有未分支的水平面。
当树完全变平时，它最终会head。

  (loop for head = (loop for x = (or head root) then (left x)
                         do (when (and x (null (left x)))
                              (swap (left x) (right x)))
                         until (or (null x) (right x))
                         finally (return x))
        for tail = (and head (left head)) then (left tail)
        while head
        do (swap (left tail) (right head))

；；这个内环是o（n）队列插入

           (loop for bubble-to = head then (left bubble-to)
                 for bubble-from = (left bubble-to)
                 until (eq bubble-from tail)
                 do (swap (right bubble-to) (right bubble-from))))

；最后，返回原始根。

  root)

关于algorithm - 将二叉树转换为链表，广度优先，常量存储/破坏性，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3411793/

Bubble

algorithm - 将二叉树转换为链表，广度优先，常量存储/破坏性