fla*_*ash 3 java algorithm binary-search-tree data-structures
我正在研究以下面试问题：
给定一个单链表，其中元素按升序排序，将其转换为高度平衡的 BST。
对于这个问题，高度平衡二叉树被定义为每个节点的两个子树的深度相差不超过1的二叉树。
我想了解下面的解决方案及其复杂性？有人可以帮助我理解它是如何工作的吗？下面的解是 O(n) 时间复杂度和 O(log n) 空间复杂度吗？
下面的算法也比“计算给定链表中的节点数。设其为n。计算节点后，我们取左n/2个节点并递归构造左子树。构造左子树后，我们分配内存为 root 并将左子树与 root 链接起来。最后，我们递归地构造右子树并将其与 root 链接。在构建 BST 的同时，我们还不断将链表头指针移至下一个，以便在每次递归调用中都有适当的指针”
public TreeNode toBST(ListNode head) {
if(head==null) return null;
return helper(head,null);
}
public TreeNode helper(ListNode head, ListNode tail){
ListNode slow = head;
ListNode fast = head;
if(head==tail) return null;
while(fast!=tail && fast.next!=tail){
fast = fast.next.next;
slow = slow.next;
}
TreeNode thead = new TreeNode(slow.val);
thead.left = helper(head,slow);
thead.right = helper(slow.next,tail);
return thead;
}
小智 5
通过将列表细分为两个相等长的列表，并使用中间的一个元素作为根，可以从排序列表构建平衡树。例如：
1. [1, 2, 3, 4, 5, 6, 7]
2. 4
/ \
[1, 2, 3] [5, 6, 7]
3. 4
/ \
2 6
/ \ / \
1 3 5 7
即使两个子列表相差 1 个元素，它们的高度最多也相差 1，从而使树保持平衡。通过采用列表的中间元素，可以保证生成的树是 BST，因为所有较小的元素都是左子树的一部分，而所有较大的元素都是右子树的一部分。
slow和fast您的代码使用两个迭代器进行工作，其中一个 ( fast) 迭代节点的速度是另一个 ( slow) 的两倍。因此，当fast到达列表的尾部或尾部之前的节点时，slow必须位于列表的中间节点，从而将列表分为两个长度相同的子列表（最多相差一个元素），然后可以递归处理，如上图所示。
该算法运行在O(n lg n). 我们先从helper的复现开始：
T(n) = n / 2 + 2 * T(n / 2)
T(1) = 1
在每次调用 时helper，我们必须找到由传递给 的两个参数定义的链表的中间节点helper。这只能分步完成n / 2，因为我们只能线性地遍历列表。除此之外helper在原始列表大小一半的链表上递归调用两次，以构建左子树和右子树。
将主定理（情况 2）应用于上述递归式，我们得到O(n lg n)。
空间复杂度还需要考虑产生的输出结构。由于输入链表的每个元素都被转换为 BST 中的一个节点，因此复杂度为O(n)。
编辑
如果忽略输出，则空间复杂度仅取决于递归深度，而递归深度又为O(lg n)，从而使空间复杂度为O(lg n)。