二重リンクリストからの平衡バイナリ検索ツリー

Question

私はdoublyLinkedListを取り込み、バランスドバイナリ検索ツリーを構築するこの関数を記述しようとしています。 TreeNode.leftは前のポインタに相当し、TreeNode.rightは次のポインタに似ています。私はここのプログラムからインスピレーションを取っていますが、そのdoesntの仕事：

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

、多分あなたはそれを試すことができますそれが動作するかどうか教えてください。