java - 将有序二叉树转换为双循环链表

Question

I have a ordered binary tree:
              4
              |
          |-------|
          2       5
          |
      |-------|
      1       3

叶子指向空。我必须创建一个双向链接列表，它应该看起来像

1<->2<->3<->4<->5

(显然5应该指向1)

节点类如下:

class Node {
    Node left;
    Node right;
    int value;

    public Node(int value)
    {
        this.value = value;
        left = null;
        right = null;
    }
}

正如您所看到的，双向链接列表也是有序的(已排序)。

问题:我必须从树中创建链接列表，而不使用任何额外的指针。树的left指针应该是列表的previous指针，树的right指针应该是next 列表指针。

我的想法:由于树是有序树，因此中序遍历会给我一个排序列表。但是在进行中序遍历时，我无法看到在哪里以及如何移动指针以形成双向链表。

P.S我检查了这个问题的一些变体，但没有一个给我任何线索。

Answer 1

听起来您需要一个方法，该方法接受对树根的 Node 引用，并返回对循环列表头的 Node 引用，其中没有新的 Node 对象被创建。我会从简单的树开始递归地处理这个问题:

   2
   |
|-----|
1     3

您没有说明树是否保证是满的，因此我们需要允许 1 和/或 3 为 null。以下方法应该适用于这个简单的树:

Node simpleTreeToList(Node root) {
    if (root == null) {
        return null;
    }
    Node left = root.left;
    Node right = root.right;
    Node head;
    if (left == null) {
        head = root;
    } else {
        head = left;
        left.right = root;
        // root.left is already correct
    }
    if (right == null) {
        head.left = root;
        root.right = head;
    } else {
        head.left = right;
        right.right = head;
        right.left = root;
    }
    return head;
}

一旦清楚了它是如何工作的，将其推广为适用于任何树的递归方法并不难。这是一个非常相似的方法:

Node treeToList(Node root) {
    if (root == null) {
        return null;
    }
    Node leftTree = treeToList(root.left);
    Node rightTree = treeToList(root.right);
    Node head;
    if (leftTree == null) {
        head = root;
    } else {
        head = leftTree;
        leftTree.left.right = root;
        root.left = leftTree.left;
    }
    if (rightTree == null) {
        head.left = root;
        root.right = head;
    } else {
        head.left = rightTree.left;
        rightTree.left.right = head;
        rightTree.left = root;
        root.right = rightTree;
    }
    return head;
}

如果我正确地涵盖了所有链接分配，这应该就是您所需要的。