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

Question

这不是一个重复的问题。

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

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

有两段代码：

https://www.techiedelight.com/construct-height-balanced-bst-from-sorted-doubly-linked-list/

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

https://www.ideserve.co.in/learn/convert-a-sorted-doubly-linked-list-to-balanced-binary-search-tree-bst

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查找列表后半部分的长度。