從排序的雙向鏈表中製作二進制搜索樹

嘿傢伙所以我正在學習編程面試問題，我陷入了這個問題。從排序的雙向鏈表中製作二進制搜索樹

我想遞歸做到這一點，但我不知道從哪裏開始。

這是算法我到目前爲止：

makeTree(head, tail){ 
    nodeMid = list/2 
    root = nodeMid 
    root.left = makeTree(head, nodeMid) 
    root.right = makeTree(nodeMid, tail)

我是否有正確的想法？任何意見都非常感謝。謝謝！

來源

2014-12-02 Beto

我立即看到的主要問題，並原諒我，如果我錯了，你不改變每個節點的列表位置。每次遞歸調用

makeTree(head, tail){ 
    nodeMid = list/2;

據我可以循環你不改變該列表的一部分使用遞歸調用走了進去看看。即你有一個整數 myint它有（0,1,2,3,4,5,6,7,8,9）每次調用遞歸它將無限地填充二進制樹的數字在列表中/ 2 您需要在每次調用時更改nodeMid的值，並使用您發送的頭部/尾部變量。

您不想保持重置根節點。您應該使用「this」運算符來設置您正在查看的當前節點的值。

開始是您正在查看的數組部分的起點並且結束爲該部分的結尾。遞歸調用將如此。您還需要在遞歸的邊界中添加

在樹中創建新節點時將BST與節點一起使用時，左右節點將設置爲null以開始。您需要創建一個新節點並調用遞歸。

Node makeTree(int head, int tail){ 
    nodeMid = (head+tail)/2; 
    this = new Node(); 
    if(head < nodeMid-1) 
    { 
     this.left = makeTree(head, nodeMid-1); 
    } 
    if(nodeMid < tail) 
    {   
     this.right = makeTree(nodeMid, tail); 
    } 
    this.setValue(list[nodeMid]); 
    return this; 
}

所有遞歸完成後，您需要設置當前節點的值並返回該節點進行創建。這將遞歸地將已排序的數組轉換爲二叉搜索樹。只需將您的雙向鏈表列入正確的列表編碼即可。

要啓動遞歸

root = makeTree(0, list.length());

來源

2014-12-02 06:49:49

感謝的人。說得通。只有一個問題，爲什麼（頭+尾）/ 2特別是如果頭部和尾部是節點。 – Beto 2014-12-03 17:17:00

頭部和尾部不能是節點，您需要能夠進行數學運算以找到您正在查看的部分的開始和結束或頭部和尾部之間的節點。爲了從列表中獲得值，我建議使用你正在查看nodeMid的數字，並通過鏈接列表遍歷鏈接或其他函數，然後將該點的值存儲在bst中 – 2014-12-04 01:05:46

如果我的答案有幫助無論如何，請標記有用的答案。 – 2014-12-04 16:03:59

邏輯

1) Get the Middle of the linked list and make it root. 
2) Recursively do same for left half and right half. 
     a) Get the middle of left half and make it left child of the root 
      created in step 1. 
     b) Get the middle of right half and make it right child of the 
      root created in step 1.

代碼

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

但由於時間複雜度，這是不是最優化的方式O（nlogn）。爲了更好地優化的解決方案來看看http://www.geeksforgeeks.org/sorted-linked-list-to-balanced-bst/

來源

2014-12-02 06:26:40 Diptendu

下面是一些要點：

獲取鏈表的中間，使之根。
對左半部和右半部遞歸地做同樣的事情。
- 獲取左半部的中間，並使其留在步驟1中
- 創建的根的孩子找右半邊的中間，使其在步驟中創建的根的右子1.

時間複雜度：O（nLogn）其中n是Linked List中的節點數。

來源

2014-12-02 06:27:35

從排序的雙向鏈表中製作二進制搜索樹

回答

相關問題