将二叉搜索树转换为双向链表

Question

这是最近一次编程面试中的问题。

问题是：给定一棵二叉树，请编写一个程序将其转换为双向链表。双向链表中的节点按照锯齿形层序遍历的顺序排列。

我的方法是：可以对树进行锯齿形层序遍历并将其存储在数组中，然后创建一个双向链表。但是问题要求使用原地解决方案。有人能帮忙解释一下递归方法应该如何使用吗？

- akash

---

顺便提一句，多么糟糕的面试问题。 - corsiKa

首先：执行旋转和拉伸操作创建一个链表。第二：设置后向指针。（也许可以将这两个步骤合并，但我懒得做你的功课）实际上：这是一个可怕的非问题。 - wildplasser

@wildplasser - 显然，OP有一个面试问题的标签。不是作业。如果我们有时间并且不懒惰，我们可以在评论和帮助方面更加包容和少一些挖苦。如果没有，就转发给别人吧。 - goldenmean

@corsika 确实很糟糕，但这是在一家顶级公司之一提出的问题，我们还有什么选择呢？如果我们想为他们工作。 - flash

顺便说一下，标题是二叉搜索树，我认为解决方案与任何二叉树的解决方案没有区别。 - Swapnil

Answer 1

这是递归方法。注意，这里的根节点将指向形成的列表中间的某个元素。因此，只需从根节点向后遍历即可获取头部。

#define NODEPTR struct node*

NODEPTR convert_to_ll(NODEPTR root){
    if(root->left == NULL && root->right == NULL)
        return root;
    NODEPTR temp = NULL;
    if(root->left != NULL){
        temp = convert_to_ll(root->left);
        while(temp->right != NULL)
            temp = temp->right;
        temp->right = root;
        root->left = temp;
    }
    if(root->right != NULL){
        temp = convert_to_ll(root->right);
        while(temp->left != NULL)
            temp = temp->left;
        temp->left = root;
        root->right = temp;
    }
    return root;
    }

- vagrawal13

---

我喜欢这个答案，我认为这是我见过的最简单的答案。 - Ahmed

哇！这比优雅和疯狂的直观还要更多！递归的力量！ - spiralmoon

复杂度O(nlogn) ... O(n)解决方案 - Ani

@Ani 两个解决方案在时间复杂度上看起来都是O(n)。 - vagrawal13

Answer 2

最简单的方法。在单个中序遍历中，只需使用O(1)空间复杂度即可实现此操作。要做到这一点，请保持一个名为lastPointer的指针，并在访问每个节点后跟踪它。使用左右

public void toll(T n) {
    if (n != null) {
        toll(n.left);
        if(lastPointer==null){
            lastPointer=n;
        }else{
            lastPointer.right=n;
            n.left=lastPointer;
            lastPointer=n;
        }
        toll(n.right);
    }
}

- Codex

Answer 3

C++ 代码：

 Node<T> *BTtoDoublyLLZigZagOrder(Node<T> *root)
 {
        if (root == 0)
            return 0;
        if (root->mLeft == 0 && root->mRight == 0)
            return root;

        queue<Node<T> *> q;
        q.push(root);
        Node<T> *head = root;
        Node<T> *prev = 0,*curr = 0;

        while(!q.empty())
        {
            curr = q.front();
            q.pop();
            if (curr->mLeft)
                q.push(curr->mLeft);
            if (curr->mRight)
                q.push(curr->mRight);
            curr->mRight = q.front();
            curr->mLeft = prev;
            prev = curr;
        }

        return head;
 }

- ami

---

尽管代码相当易读，但最好添加伪代码版本或技术解释，因为问题与编程语言无关。 - Orbling

Answer 4

在斯坦福图书馆链接中提到的解决方案是将BST转换为循环DLL的完美解决方案，下面的解决方案并不完全是BST转换为循环DLL，但是可以通过连接DLL的末端来实现循环DLL。这也不完全是Zig Zag有序树到DLL的转换。

注意：这个解决方案并不是BST转换为循环DLL的完美转换，但它是一个易于理解的技巧。

JAVA代码

public Node bstToDll(Node root ){
        if(root!=null){
            Node lefthead = bstToDll(root.left); // traverse down to left 
            Node righthead = bstToDll(root.right); // traverse down to right
            Node temp = null;
            /*
             * lefthead represents head of link list created in left of node
             * righthead represents head of link list created in right
             * travel to end of left link list and add the current node in end
             */
            if(lefthead != null) {
                temp = lefthead;
                while(temp.next != null){
                    temp = temp.next;
                }
                temp.next = root;
            }else{
                lefthead = root;
            }
            root.prev = temp;
            /*
             *set the next node of current root to right head of right list
             */
            if(righthead != null){
                root.next = righthead;
                righthead.prev = root;
            }else{
                righthead = root;
            }
            return lefthead;// return left head as the head of the list added with current node
        }
        return null;
}

希望这能帮助到某些人。

- Anupam Gupta

Answer 5

不使用全局变量的反向中序遍历 - c# 实现。在调用时，最初将 null 传递给 right 参数。最终返回值是双向链表的 head。

public static Node ToDLL(Node node, Node right)
{
    if (node == null)
        return null;

    var rnd = ToDLL(node.Right, right);

    if (rnd != null)
    {
        node.Right = rnd;
        rnd.Left = node;
    }
    else
    {
        node.Right = right;
        if (right!= null)
            right.Left= node;
    }
    return ToDLL(node.Left, node) ?? node;
}

- Saravanan

Answer 6

struct node{
int value;
struct node *left;
struct node *right;
};
typedef struct node Node;

Node * create_node(int value){
  Node * temp =  (Node *)malloc(sizeof(Node));
  temp->value = value;
  temp->right= NULL;
  temp->left = NULL;
  return temp;
}
Node * addNode(Node *node, int value){
  if(node == NULL){
    return create_node(value);
  }
  else{
    if (node->value > value){
        node->left = addNode(node->left, value);
    }
    else{
        node->right = addNode(node->right, value);
    }
  }
  return node;
}

void treeToList(Node *node){

    Queue *queue = NULL;
    Node * last = NULL;
    if(node == NULL)
            return ;

    enqueue(&queue, node);
    while(!isEmpty(queue)){
       /* Take the first element and put 
          both left and right child on queue */
            node = front(queue);
            if(node->left)
                    enqueue(&queue, node->left);
            if(node->right)
                    enqueue(&queue, node->right);
            if(last != NULL)
                    last->right = node;
            node->left = last;
            last = node;
            dequeue(&queue);
      }
  } 
  /* Driver program for the function written above */
 int main(){
    Node *root = NULL;
   //Creating a binary tree
    root = addNode(root,30);
    root = addNode(root,20);
    root = addNode(root,15);
    root = addNode(root,25);
    root = addNode(root,40);
    root = addNode(root,37);
    root = addNode(root,45);

    treeToList(root);

    return 0;
}

队列API的实现可以在以下链接中找到： http://www.algorithmsandme.com/2013/10/binary-search-tree-to-doubly-linked.html

- jitsceait

Answer 7

node* convertToDLL(node* root, node*& head, node*& tail)
{
    //empty tree passed in, nothing to do
    if(root == NULL)
        return NULL;

    //base case
    if(root->prev == NULL && root->next == NULL)
        return root;

    node* temp = NULL;
    if(root->prev != NULL)
    {
        temp = convertToDLL(root->prev, head, tail);

        //new head of the final list, this will be the left most
        //node of the tree.
        if(head == NULL)
        {
            head=temp;
            tail=root;
        }

        //create the DLL of the left sub tree, and update t
        while(temp->next != NULL)
            temp = temp->next;
        temp->next = root;
        root->prev= temp;
        tail=root;
    }

    //create DLL for right sub tree
    if(root->next != NULL)
    {
        temp = convertToDLL(root->next, head, tail);
        while(temp->prev != NULL)
            temp = temp->prev;
        temp->prev = root;
        root->next = temp;

        //update the tail, this will be the node with the largest value in
        //right sub tree
        if(temp->next && temp->next->val > tail->val)
            tail = temp->next;
        else if(temp->val > tail->val)
            tail = temp;
    }
    return root;
}

void createCircularDLL(node* root, node*& head, node*& tail)
{
    convertToDLL(root,head,tail);

    //link the head and the tail
    head->prev=tail;
    tail->next=head;
}

int main(void)
{

    //create a binary tree first and pass in the root of the tree......
    node* head = NULL;
    node* tail = NULL;
    createCircularDLL(root, head,tail);

    return 1;
}

- gilla07

Answer 8

我们可以使用中序遍历并跟踪先前访问的节点。对于每个访问的节点，可以分配前一个节点的右侧和当前节点的左侧。

void BST2DLL(node *root, node **prev, node **head)
{
    // Base case
    if (root == NULL) return;

    // Recursively convert left subtree
    BST2DLL(root->left, prev, head);

    if (*prev == NULL) // first iteration
        *head = root;
    else
    {
        root->left = *prev;
        (*prev)->right = root;
    }
    *prev = root; // save the prev pointer 

    // Finally convert right subtree
    BST2DLL(root->right, prev, head);
}

- learner

Answer 9

这是Java代码。复杂度为O(N)。我还添加了一些测试用例来解决这个问题。

public class BinaryToDoubleLinkedList {

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

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

    static class Pair {
        Node head;
        Node tail;

        public Pair(Node head, Node tail) {
            this.head = head;
            this.tail = tail;
        }
    }

    static Pair convertToDoubleLinkedList(Node root) {
        return convert(root);
    }

    static Pair convert(Node root) {
        if (root == null) return new Pair(null, null);

        Node head, last;

        Pair left = convert(root.left);
        if (left.tail != null) {
            left.tail.right = root;
            root.left = left.tail;
            head = left.head;
        } else {
            head = root;
        }

        Pair right = convert(root.right);
        if (right.head != null) {
            right.head.left = root;
            root.right = right.head;
            last = right.tail;
        } else {
            last = root;
        }

        return new Pair(head, last);
    }

    static void Print(Node root, boolean fromLeft) {
        System.out.println("---------");
        if (fromLeft) {
            while (root != null) {
                System.out.print(root.value + ",");
                root = root.right;
            }
        } else {
            while (root != null) {
                System.out.print(root.value + ",");
                root = root.left;
            }
        }

        System.out.println();
    }

    public static void main(String[] args) {
        test1();
        test2();
        test3();
    }

    // test 1: normal test case
    public static void test1() {
        Node root = new Node(10, null, null);
        root.left = new Node(12, null, null);
        root.right = new Node(15, null, null);

        root.left.left = new Node(25, null, null);
        root.left.right = new Node(30, null, null);
        root.right.left = new Node(36, null, null);

        Pair res = convertToDoubleLinkedList(root);
        Print(res.head, true);
        Print(res.tail, false);
    }

    // test 2: binary tree as linked list
    public static void test2() {
        Node root = new Node(1, null, null);
        root.left = new Node(2, null, null);
        root.left.left = new Node(3, null, null);
        root.left.left.left = new Node(4, null, null);

        Pair res = convertToDoubleLinkedList(root);
        Print(res.head, true);
        Print(res.tail, false);
    }

    // test 3: null and single
    public static void test3() {
        Node root = new Node(1, null, null);
        Pair res = convertToDoubleLinkedList(root);
        Print(res.head, true);
        Print(res.tail, false);

        res = convertToDoubleLinkedList(null);
        Print(res.head, true);
        Print(res.tail, false);
    }
}

- hqt

Answer 10

希望这能对你有所帮助。

class Solution(){
public:
    TreeNode* convertBST2DLL(TreeNode* root){
        TreeNode left, right;
        convert(root, &left, &right);
        TreeNode* head = left.right;
        head->left = NULL;
        right.left->right = NULL;
        return head;
    }   
    void convert(TreeNode* root, TreeNode* left, TreeNode* right){
        if(root->left == NULL){
            left->right = root;
            root->left = left;
        }
        else{
            convert(root->left, left, root);
        }
        if(root->right == NULL){
            right->left = root;
            root->right = right;
        }
        else{
            convert(root->right, root, right);
        }
    }
};

- chunhui li