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

在最近的编码访谈中询问了这个问题。将二叉搜索树转换为双向链表

问：给定一个二叉树，编写一个程序将其转换为双向链表。在双向链表中的节点被安排在由曲折级序遍历

我的做法形成了序列

我总是可以做树的曲折级序遍历并储存起来在一个数组中然后创建一个双链表。但问题需要一个就地解决方案。任何人都可以帮助解释应该使用递归方法吗？

来源

2012-07-16 akash

+11

作为一个便笺，多么糟糕的面试问题。 – corsiKa 2012-07-16 20:22:27

首先：执行旋转和strech到链接列表。第二：设置反向指示器。（也许你可以把步骤结合起来，但我懒得做你的功课）而且的确：这是一个可怕的非问题。 – wildplasser 2012-07-16 20:26:11

@wildplasser请你详细说明。谢谢你的回复 – akash 2012-07-16 20:28:59

这是递归的方法。注意，这里的root会指向一些中间元素所形成的列表。所以，只要从根开始回溯到头部即可。

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

来源

2012-07-17 20:02:28 vagrawal13

我喜欢这个答复，我认为这是我见过的最简单的一个 – 2012-10-09 16:24:59

哇！这不仅仅是优雅而且疯狂直截了当！递归的力量！ – 2013-11-17 21:06:55

复杂性O（nlogn）... O（n）解决方案https://stackoverflow.com/a/26928591/5947203 – Ani 2017-07-16 16:48:08

在斯坦福库链接提到的解决方案是BST到圆形DLL完美的解决方案，下面的解决方案是不完全的BST到圆形DLL转换但圆形DLL可以通过加入一个DLL的端部来实现。它不完全是锯齿形的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; 
}

希望它可以帮助一些一

来源

2012-09-06 16:27:22

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

来源

2012-11-26 15:09:47 ami

虽然代码非常易读，但最好添加一个伪代码版本或技术说明，因为问题是语言不可知的。 – Orbling 2012-11-26 15:28:33

我们将使用两个前哨节点头部和尾部，并对树进行按顺序遍历。第一次，我们必须将头部连接到最小的节点，反之亦然，并且将最小的节点连接到尾部，反之亦然。在第一次之后，我们只需要重新连接当前节点和尾部，直到遍历完成。遍历后，我们将删除前哨节点并正确地重新链接头部和尾部。

public static Node binarySearchTreeToDoublyLinkedList(Node root) { 

    // sentinel nodes 
    Node head = new Node(); 
    Node tail = new Node(); 

    // in-order traversal 
    binarySearchTreeToDoublyLinkedList(root, head, tail); 

    // re-move the sentinels and re-link; 
    head = head.right; 
    tail = tail.left; 

    if (head != null && tail != null) { 
     tail.right = head; 
     head.left = tail; 
    } 

    return head; 
} 

/** In-order traversal **/ 
private static void binarySearchTreeToDoublyLinkedList(Node currNode, Node head, Node tail) { 
    if (currNode == null) { 
     return; 
    } 


    // go left 
    // 

    binarySearchTreeToDoublyLinkedList(currNode.left, head, tail); 

    // save right node for right traversal as we will be changing current 
    // node's right to point to tail 
    // 

    Node right = currNode.right; 

    // first time 
    // 

    if (head.right == null) { 

     // fix head 
     // 

     head.right = currNode; 
     currNode.left = head; 

     // fix tail 
     // 

     tail.left = currNode; 
     currNode.right = tail; 

    } else { 

     // re-fix tail 
     // 

     Node prev = tail.left; 

     // fix current and tail 
     // 

     tail.left = currNode; 
     currNode.right = tail; 

     // fix current and previous 
     // 

     prev.right = currNode; 
     currNode.left = prev; 
    } 

    // go right 
    // 

    binarySearchTreeToDoublyLinkedList(right, head, tail); 
}

来源

2013-05-05 08:51:30

最简单的方法。在单次序遍历中，只有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); 
    } 
}

来源

2014-11-14 11:05:49 vinoth10

复杂性O（N）...因为它是一个简单的遍历... – Ani 2017-07-16 16:48:41

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

来源

2015-01-25 15:41:49 gilla07

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

来源

2015-03-14 14:19:55 jitsceait

我们可以用序遍历并跟踪以前访问过的节点。对于每个访问节点，可以分配前一个节点权限和当前节点。

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

来源

2015-04-18 07:11:56 learner

希望这会对你有帮助。

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

来源

2016-04-11 10:22:56

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

回答

相关问题