[LC]109.有序链表转换二叉搜索树

题目

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

分析

分治

我们将链表中间偏左的结点$m*$作为根节点构建BST，由此将原问题规约为两个规模更小的子问题，分别递归求解，得到左子树和右子树，将其和根结点组合后返回即可。

代码

class Solution {
public:
    ListNode *findMid(ListNode *head, ListNode *end)
    {
        ListNode *slow = head, *fast = head;
        while (fast->next != end && fast->next->next != end)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    TreeNode *buildBST(ListNode *head, ListNode *end)
    {
        if (head == end) return nullptr;
        auto mid = findMid(head, end);
        TreeNode *root = new TreeNode(mid->val);
        root->left = buildBST(head, mid);
        root->right = buildBST(mid->next, end);
        return root;
    }
    TreeNode* sortedListToBST(ListNode* head) {
        return buildBST(head, nullptr);
    }
};

时间复杂度

每次递归的时候，为了找到中间的结点，我们需要$O(n)$的时间。

由此得到递推方程$W(n) = 2W(n/2) + O(n).$

由主定理，解得$W(n) = \Theta(nlogn).$

空间复杂度

空间复杂度为递归深度$O(logn).$

优化

可以看到，由于链表不具有随机访问的能力，我们为了找到中间结点，需要花费$O(n)$的时间。

为了减少这个时间，一种可能的方法是以空间换时间，将链表中的元素存储进数组中，这样就可以在$O(1)$的时间内访问到中间结点了，但是这样会导致空间复杂度变为$O(n)$.

那有什么办法可以既保证空间复杂度不改变，又能够降低时间复杂度呢？

观察建树的过程，我们先初始化根结点，然后去递归的建立左子树和右子树，但建立左子树的过程中，根结点的唯一作用就是作为边界，实际只会用到根节点左边的结点。因此，我们可以用下标来代替根节点，先建立左子树，然后建立根结点，之后再建立右子树。这个过程很类似中序遍历的过程，因此我们可以再每次递归的时候，将头结点后移，这样在递归处理完左子树之后，头结点的位置刚好指向我们需要的中间结点的位置，从而无需花费$O(n)$的时间复杂度去定位中间节点。

代码：

class Solution {
public:
    int getLength(ListNode *head)
    {
        int length = 0;
        while (head) 
        {
            ++length;
            head = head->next;
        }
        return length;
    }
    // [l, r]
    TreeNode *buildBST(ListNode *&head, int l, int r)
    {
        if (l > r) return nullptr;
        auto root = new TreeNode();
        int m = l + ((r - l) >> 1);
        root->left = buildBST(head, l, m - 1);
        root->val = head->val;
        head = head->next;
        root->right = buildBST(head, m + 1, r);
        return root;
    }
    TreeNode* sortedListToBST(ListNode* head) {
        int length = getLength(head);
        return buildBST(head, 0, length - 1);
    }
};

时间复杂度

递推方程$W(n) = 2W(n/2) + O(1).$

由主定理，$W(n) = \Theta(n).$

空间复杂度

空间复杂度等于递归深度$O(logn).$