Balancierter binärer Suchbaum aus doppelt verknüpfter Liste

Question

Ich versuche, diese Funktion zu schreiben, die eine doublyLinkedList aufnimmt und einen ausgeglichenen binären Suchbaum erzeugt. Der TreeNode.left entspricht dem vorherigen Zeiger und TreeNode.right ist wie der nächste Zeiger. Ich nehme Inspiration aus dem Programm hier aber das funktioniert nicht:

http://www.geeksforgeeks.org/in-place-conversion-of-sorted-dll-to-balanced-bst/

private static TreeNode constructBST2(TreeNode head, int m, int n) { 
    TreeNode temp = null; 
    if (m < n) { 
     int mid = m + (n - m)/ 2; 
     TreeNode left = constructBST2(head, m, mid); 
     temp = head; 
     temp.left = left; 
     head = head.right; 
     temp.right = constructBST2(head, mid + 1, n); 
    } 
    return temp; 
} 

Answer 1

Lassen Sie mich versuchen:

private static TreeNode constructBST2(TreeNode root, int r, int m, int n) { 
    if (m < n) { 
     int leftTreeMid = m + (int)Math.ceil((r - m)/2); 
     int delta = r - leftTreeMid; 
     TreeNode left = root; 
     for (int i = 0; i < delta; i++) 
      left = left.left; 
     root.left = left; 
     constructBST2(left, leftTreeMid, m, r - 1); 

     int rightTreeMid = r + (int)Math.ceil((n - r)/2); 
     delta = rightTreeMid - r; 
     TreeNode right = root; 
     for(int i = 0; i < delta; i++) 
      right = right.right; 
     root.right = right; 
     constuctBST2(right, rightTreeMid, r + 1, n); 
    } 
    return root; 
} 

ich es gar nicht versucht haben, vielleicht können Sie es versuchen und sag mir, ob es funktioniert.