Сбалансированное двоичное дерево поиска из дважды связанного списка

Question

Я пытаюсь написать эту функцию, которая принимает в doublelyLinkedList и создает сбалансированное двоичное дерево поиска на месте. TreeNode.left эквивалентен предыдущему указателю, а TreeNode.right - как следующий указатель. Я беру вдохновение из программы здесь, но это не работает:

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

Позвольте мне попробовать:

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

Я не пробовал его на всех, может быть, вы можете попробовать его и скажите мне, если это сработает.