将排序的双链表转换为平衡的二叉搜索树？这种递归是如何工作的？

Question

这不是一个重复的问题。

当我们将排序数组转换为BST时，我们确实从n/2元素的左部分和右部分得到左和右。而当我们试图转换双链表时，为什么我们从(len-(len/2)-1)得到正确的结果。

基本上，我想明白为什么会有差别，以及如何向某人解释。

public static Node buildBalancedBST(List<Node> nodes, int start, int end)
    {
        // base case
        if (start > end) {
            return null;
        }
 
        // find the middle index
        int mid = (start + end) / 2;
 
        // The root node will be node present at the mid index
        Node root = nodes.get(mid);
 
        // recursively construct left and right subtree
        root.prev = buildBalancedBST(nodes, start, mid - 1);
        root.next = buildBalancedBST(nodes, mid + 1, end);
 
        // return root node
        return root;
    }

private ListNode convertDllToBST(int len) {
        if (len == 0) {
            return null;
        }
 
        ListNode left = convertDllToBST(len / 2);
        ListNode root = head;
        root.prev = left;
        head = head.next;
        ListNode right = convertDllToBST(len - (len / 2) - 1);
        root.next = right;
        return root;
    }

Answer 1

这两个公式正在进行不同的计算。

在第一段代码中，start+end/2查找数组中间元素的索引（数组中要转换的部分）。

而在第二段代码中，len-(len/2)-1查找列表后半部分的长度。