將二叉搜索樹轉換爲雙向鏈表

Question

在最近的編碼訪談中詢問了這個問題。

問：給定一個二叉樹，編寫一個程序將其轉換爲雙向鏈表。在雙向鏈表中的節點被安排在由曲折級序遍歷

我的做法形成了序列

我總是可以做樹的曲折級序遍歷並儲存起來在一個數組 中然後創建一個雙鏈表。 但問題需要一個就地解決方案。 任何人都可以幫助解釋應該使用遞歸方法嗎？

Answer 1

這是遞歸的方法。注意，這裏的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; 
    } 

Answer 2

在斯坦福庫鏈接提到的解決方案是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; 
} 

希望它可以幫助一些一

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

Answer 4

我們將使用兩個前哨節點頭部和尾部，並對樹進行按順序遍歷。第一次，我們必須將頭部連接到最小的節點，反之亦然，並且將最小的節點連接到尾部，反之亦然。在第一次之後，我們只需要重新連接當前節點和尾部，直到遍歷完成。遍歷後，我們將刪除前哨節點並正確地重新鏈接頭部和尾部。

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

Answer 5

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

Answer 6

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

Answer 7

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

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

Answer 9

希望這會對你有幫助。

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