109. 有序链表转换二叉搜索树 ●●

109. 有序链表转换二叉搜索树 ●●

描述

给定一个单链表的头节点 head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。

示例

输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。

题解

1. 分治 链表中位数

与108. 将有序数组转换为二叉搜索树 ● 类似，但是此题涉及到链表的操作问题，因为链表不能像数组一样随机存取，需要通过顺序访问来获取到中位数的位置。

此处通过快慢指针来得到中位数，快指针比慢指针快一倍，当快指针到达终点时，慢指针则指向中位数。

然后通过分治递归，构造左右子树。

由于题目中给定的链表为单向链表，访问后继元素十分容易，但无法直接访问前驱元素。因此在找出链表的中位数节点 mid 之后，如果设定「左闭右开」的关系，我们就可以直接用 (left,mid) 以及(mid->next,right) 来表示左右子树对应的列表了。并且，初始的列表也可以用 (head,null) 方便地进行表示，其中 null表示空节点。

• 时间复杂度：$O(n\log n)$，其中 n 是链表的长度。
  设长度为 n 的链表构造二叉搜索树的时间为 $T(n)$，递推式为 $T(n)=2\cdot T(n/2)+O(n)$，根据主定理，$T(n)=O(n\log n)$。

• 空间复杂度：$O(\log n)$，这里只计算除了返回答案之外的空间。平衡二叉树的高度为 $O(\log n)$，即为递归过程中栈的最大深度，也就是需要的空间。

class Solution {
public:
    ListNode* getMid(ListNode* head, ListNode* end){
        ListNode* slow = head;                          // 快慢指针
        ListNode* fast = head;
        while(fast != end && fast->next != end){
            slow = slow->next;
            fast = fast->next->next;                    // 快指针是慢指针的两倍，因此慢指针为中位数
        }
        return slow;
    }

    TreeNode* bulidTree(ListNode* head, ListNode* end){     // 左闭右开
        if(head == end) return nullptr;                     // 当前节点以遍历过
        ListNode* mid = getMid(head, end);                  // 找到链表中位数
        TreeNode* root = new TreeNode(mid->val);            // 建立树根节点
        root->left = bulidTree(head, mid);                  // 左子树，左闭右开
        root->right = bulidTree(mid->next, end);            // 右子树
        return root;
    }

    TreeNode* sortedListToBST(ListNode* head) {
        return bulidTree(head, nullptr);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2. 分治 + 中序遍历优化

方法一的时间复杂度的瓶颈在于寻找中位数节点。

由于构造出的二叉搜索树的中序遍历结果就是链表本身，因此我们可以将分治和中序遍历结合起来，减少时间复杂度。

具体地，设当前链表的左端点编号为 left，右端点编号为 right，包含关系为「双闭」，即 left 和 right 均包含在链表中。

链表节点的编号为 [0,n)。中序遍历的顺序是「左子树 - 根节点 - 右子树」，那么在分治的过程中，我们不用急着找出链表的中位数节点，而是使用一个占位节点，等到中序遍历到该节点时，再填充它的值（更新 head 节点）。

我们可以通过计算编号范围来进行中序遍历：

• 中位数节点对应的编号为 $mid=(left+right+)/2$；
• 左右子树对应的编号范围分别为 $[left,mid-1]$ 和 $[mid+1,right]$。

如果 $left>right$，那么遍历到的位置对应着一个空节点，否则对应着二叉搜索树中的一个节点。

这样一来，我们其实已经知道了这棵二叉搜索树的结构，并且题目给定了它的中序遍历结果，那么我们只要对其进行中序遍历，就可以还原出整棵二叉搜索树了。

• 时间复杂度：$O(n)$，其中 n 是链表的长度。
  设长度为 n 的链表构造二叉搜索树的时间为 T(n)，递推式为 $T(n)=2\cdot T(n/2)+O(1)$，根据主定理，$T(n)=O(n)$。
• 空间复杂度：$O(logn)$，这里只计算除了返回答案之外的空间。平衡二叉树的高度为 $O(\log n)$，即为递归过程中栈的最大深度，也就是需要的空间。

注意：
递归函数中用head = head -> next;来表示中序遍历时链表节点的更新过程；
head 传参需要加 &，才能真正改变链表节点的位置。

class Solution {
public:
    TreeNode* buildTree(ListNode*& head, int left, int right){     // 双闭
        if(left > right) return nullptr;                // 空节点
        int mid = (left + right) >> 1;                  // 中位数节点
        TreeNode* root = new TreeNode();                
        root->left = buildTree(head, left, mid - 1);    // 左
        root->val = head->val;                          // 中，实际是从最左节点开始赋值，即中序遍历得到的链表
        head = head->next;                              // 中，更新链表节点，head 传参需要加 &
        root->right = buildTree(head, mid + 1, right);  // 右
        return root;
    }

    TreeNode* sortedListToBST(ListNode* head){
        int len = 0;
        ListNode* curr = head;
        while(curr != nullptr){
            ++len;                                      // 链表长度
            curr = curr->next;
        }
        return buildTree(head, 0, len-1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23