将排序链接列表转换为平衡BST
我正在做以下面试问题：
给定元素按升序排序的单链接列表，将其转换为高度平衡的BST。 对于这个问题，高度平衡二叉树被定义为一个二叉树，其中每个节点的两个子树的深度不超过1。
我试图理解下面的解决方案及其复杂性？有人能帮我理解一下它的工作原理吗？在解O(n)时间复杂度和O(log n)空间复杂度以下吗？
下面的算法也比“计算给定链表中的节点数更好，假设为n。在计算节点后，我们取左n/2节点并递归地构造左子树；在构造左子树之后，我们为根分配内存，并将左子树与根连接起来。最后，我们递归地构造右子树并将其与根连接。在构造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;
}回答 1
Stack Overflow用户
发布于 2018-12-03 07:59:05
BST-建筑
通过将列表细分为两个同样长的列表，可以从排序列表构建平衡树，中间有一个元素作为根。例如：
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，从而使树保持平衡。通过接受列表的中间元素，结果树肯定是一个BST，因为所有较小的元素都是左侧子树的一部分，而右侧子树的所有较大元素都是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两次，以构建左和右子树。
将主定理((analysis_of_algorithms%29)(个案) 2)应用于上述递推，得到了O(n lg n).
空间复杂性
空间复杂性也需要考虑产出结构。由于输入链接列表的每个元素都被转换为BST中的一个节点，复杂性为O(n)。
编辑
如果忽略输出，空间复杂度仅取决于递归深度，而递归深度又是O(lg n)，从而使空间复杂度O(lg n)。
https://stackoverflow.com/questions/53588240
复制相似问题
腾讯云开发者
