将有序二进制树转换为双循环链接列表

Question

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

叶子指向null.我必须创建一个看起来像双重链接的列表

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列表的指针.

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

PS我检查了这个问题的一些变化,但没有一个给我任何线索.

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;
}

如果我正确地覆盖了所有链接分配,那么这应该就是您所需要的.