data-structures - 二重連結リストからの平衡二分探索木

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

私はまったく試していません。試してみて、うまくいくかどうか教えてください。