这是不做作业，我不需要回答这个问题，但现在我已经成为痴迷：）

现在的问题是：

在设计一个算法，用来破坏性压扁一个二叉树链表，广度优先。好吧，很容易。只需建立一个队列，做你不得不这样做。 这是热身。现在，随着不断的存储实现它（递归，如果你可以用它找出一个答案，是对数的存储，而不是常量）。

我找到了一个解决方案，以大约一年回在互联网上这个问题，但现在我已经忘记了，我想知道：）

诀窍，只要我还记得，其中用树来实现队列，取算法的破坏性的优势。当你链接的列表中，你也正在力推一个项目到队列。

每次我试图解决这个问题，我失去节点（如每个链接我的下一个节点/添加到队列中的时间），我需要额外的存储空间，或无法计算出令人费解的方法，我需要得到回有我需要的指针的节点。

即使是链接到原来的文章/后会:)谷歌是给我任何喜悦，对我很有帮助。

编辑：

热雷米指出，有一个相当简单的（众所周知的回答）如果你有一个父指针。虽然我现在认为他是正确的约含父指针原来的解决方案，我真的想解决问题，而不吧：）

精致的要求使用这个定义的节点：

 结构tree_node
{
  int值;
  tree_node *离开;
  tree_node *权利;
};
 

解决方案

的理念：

您可以构建沿树的孩子们留下的链接列表。与此同时，该列表的右侧孩子用于保持下一个子树的一个队列中插入在尾

伪code算法：

（编辑：改写为清楚起见的）

在一个节点有三个组成部分：一个值，一提到它的左子，并参考其右孩子。引用可以为null。 该函数变换这类节点的二进制树到单个链表 将参考根节点为参数根， 循环，用尾从左边的孩子开始根： 交换的左子尾与根的右子， 循环（ O（N）的队列中插入），用泡沫 - 从根启动和泡沫 - 从永远的左子泡到， 交换的右子泡到与'bubble-from`的右孩子， 事先泡到和泡沫 - 从来左手的孩子， 直到泡沫 - 从达到尾， 事先尾来的左子， ，而尾不为空。 最后，返回头。单链表现在沿左边儿童运行。

插图

起始树（我认为它应该是一个完整的树;如果节点丢失，他们应该结束这样做你可以试着赋予意义的其他案件，但也有针对几个不同的可能性，。它涉及到很多摆弄）：

  1
          / \
      2 3
    / \ / \
  4 5 6 7
 / \ / \ / \ / \
8 9 A B C D电子网
 

请注意，这些不是一定的节点的值，也只是编号进行显示。

1次迭代（注意清单从 1 成形 3 和子树的根队列后的树在 4 和 5 ）：

 头
                  v
                  1
               / \
    尾2 4
      V / \ / \
      3 5 8 9
    / \ / \
  6 7 A B
 / \ / \
维库电子
 

经过3次迭代（列表现在 1 到 5 ，以及队列拥有根植于子树 6 到 9 ）：

 头
                     v
                     1
                  / \
               2 6
             / \ / \
           3 7 C D
          / \ / \
         4 8电子网
        / \
尾＆GT; 5 9
      / \
     A B
 

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

 头
                         v
                         1
                        / \
                       2 B
                      / \
                     的3C
                    / \
                   4 D
                  / \
                 5专
                / \
               6 F
              /
             7
            /
           8
          /
         9
        /
尾＆GT;一个
 

房地产code（Lisp的）

这是节点类：

 （defclass节点（）
  （（左：存取左）
   （右图：访问权）
   （价值：存取值）））
 

一个有用的帮手：

 （defmacro掉期（A，B）
  `（psetf，A，B
          ，B，A））
 

转换函数（编辑：改写为清楚起见的）：

 （defun函数压扁完成树（根）
  （然后循环的尾部=（和根（左根））（左尾）
        而尾
        做（互换（左尾）（右根））
           （循环的泡沫来=根则（左泡到）
                 为气泡从=（左气泡通）
                 直到（EQ泡沫的尾巴）
                 做（交换（右气泡通）（右气泡从））））
  根）
 

不可逆操作铁血树：

我已经重写了上述允许任意参差不齐的树木。你不能重建从这个原来的树了，但。

 （defun函数压扁树（根）
 

;;内环这里一直头的作为，但不平整的子树的根， ;;即第一支，节点 ;;而在同一时间熨烫所有从根无支链的水平向左。 ;;它结束了零当树被完全夷为平地。

 （环路头=（回路X =（或头根），然后（左X）
                         做（当（以及x（空（左x）的））
                              （互换（左X）（右X）））
                         直到（或（空X）（右X））
                         最后（返回X））
        对于尾部=（和头部（左头）），然后（左尾）
        而头
        做（互换（左尾）（右头））
 

;;这个内循环是的 O（N）的队列中插入

 （循环的泡沫来=头，然后（左泡到）
                 为气泡从=（左气泡通）
                 直到（EQ泡沫的尾巴）
                 做（交换（右气泡通）（右气泡从））））
 

;;最后，回到原来的根。

 根）
 

This is not homework, and I don't need to answer it, but now I have become obsessed :)

The problem is:

Design an algorithm to destructively flatten a binary tree to a linked list, breadth-first. Okay, easy enough. Just build a queue, and do what you have to. That was the warm-up. Now, implement it with constant storage (recursion, if you can figure out an answer using it, is logarithmic storage, not constant).

I found a solution to this problem on the Internet about a year back, but now I've forgotten it, and I want to know :)

The trick, as far as I remember, involved using the tree to implement the queue, taking advantage of the destructive nature of the algorithm. When you are linking the list, you are also pushing an item into the queue.

Each time I try to solve this, I lose nodes (such as each time I link the next node/add to the queue), I require extra storage, or I can't figure out the convoluted method I need to get back to a node that has the pointer I need.

Even the link to that original article/post would be useful to me :) Google is giving me no joy.

Edit:

Jérémie pointed out that there is a fairly simple (and well known answer) if you have a parent pointer. While I now think he is correct about the original solution containing a parent pointer, I really wanted to solve the problem without it :)

The refined requirements use this definition for the node:

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

解决方案

The Idea:

You can build the linked list along the left children of the tree. At the same time, the right children of that list are used to hold a queue of the next subtrees to insert at the tail.

The algorithm in pseudo code:

(edit: rewritten for clarity)

A node has three components: a value, a reference to its left child, and a reference to its right child. The references may be null. The function to transform a binary tree of such nodes into a single linked list takes a reference to the root node as parameter root, loops, with tail starting from the left child of root: swap the left child of tail with the right child of root, loop (O(n) queue insertion), with bubble-to starting from root and bubble-from always the left child of bubble-to, swap the right child of bubble-to with the right child of ´bubble-from`, advance bubble-to and bubble-from to their left children, until bubble-from reaches tail, advance tail to its left child, while tail is not null. Finally, return head. The single linked list now runs along the left children.

Illustration

The starting tree (I believe that it should be a complete tree; if nodes are missing, they should do so from the end. You could try to give meaning to other cases, but there are several different possibilities for that, and it involves a lot of fiddling):

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

Note that these are not necessarily the values of the nodes, they are just numbered for display purposes.

The tree after 1 iteration (note the list forming from 1 to 3 and the queue of the subtrees rooted in 4 and 5):

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

after 3 iterations (the list is now 1 to 5, and the queue holds the subtrees rooted in 6 to 9):

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

and after 8 iterations (almost done):

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

Real Code (Lisp)

This is the node class:

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

A useful helper:

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

The conversion function (edit: rewritten for clarity):

(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)

Irreversible Operation for Jagged Trees:

I have rewritten the above to allow for arbitrary jagged trees. You cannot reconstruct the original tree from this anymore, though.

(defun flatten-tree (root)

;; The inner loop here keeps head at the root of the as-yet unflattened sub-tree, ;; i.e. the node of the first branch, ;; while at the same time ironing all from the root unbranched levels to the left. ;; It ends up nil when the tree is completely flattened.

  (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))

;; This inner loop is the O(n) queue insertion

           (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))))

;; Finally, return the original root.

  root)