力扣每日一题109：有序链表转换二叉搜索树

题目

中等

给定一个单链表的头节点  head ，其中的元素 按升序排序 ，将其转换为 

平衡

 二叉搜索树。

示例 1:

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

示例 2:

输入: head = []
输出: []

提示:

• head 中的节点数在[0, 2 * 104] 范围内
• -105 <= Node.val <= 105

面试中遇到过这道题?

1/5

是

否

通过次数

161.6K

提交次数

211K

通过率

76.6%

思路

和有序数组转换为二叉搜索树的的思路一样，都是以中间值为根，然后递归建立左右子树。区别就是：如果是数组的话，直接用下标就能找到中间元素，如果是有序链表的话，用快慢指针寻找中间元素、或是知道链表长度情况下，根据遍历次数寻找中间元素。

链表和树的结点结构

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 /*

方法一：根据遍历次数寻找中间元素。

class Solution {
public:
    TreeNode *build(ListNode *head,int lo,int hi)
    {
        if(lo>hi) return NULL;
        //找中间位置
        int mid=(lo+hi)/2;
        ListNode *middle=head;
        for(int i=0;i<mid-lo;i++)
        {
            middle=middle->next;
        }
        //建根，递归建立左右子树
        TreeNode *root=new TreeNode(middle->val);
        root->left=build(head,lo,mid-1);
        root->right=build(middle->next,mid+1,hi);
        return root;
    }
    TreeNode* sortedListToBST(ListNode* head) {
        int n=0;
        ListNode *p=head;
        while(p)
        {
            n++;
            p=p->next;
        }
        return build(head,0,n-1);
    }
};

方法二：快慢指针寻找中间元素

使用快慢指针寻找中间元素是链表题目的基操。原理就是，设置一个快指针fast和一个慢指针slow，快指针的速度是慢指针的两倍，当快指针走到最后的时候，慢指针就到了中间位置。

class Solution {
public:
    ListNode* getMedian(ListNode* left, ListNode* right) {
        ListNode* fast = left;
        ListNode* slow = left;
        while (fast != right && fast->next != right) {
            fast = fast->next;
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }

    TreeNode* buildTree(ListNode* left, ListNode* right) {
        if (left == right) {
            return nullptr;
        }
        ListNode* mid = getMedian(left, right);
        TreeNode* root = new TreeNode(mid->val);
        root->left = buildTree(left, mid);
        root->right = buildTree(mid->next, right);
        return root;
    }

    TreeNode* sortedListToBST(ListNode* head) {
        return buildTree(head, nullptr);
    }
};

方法三：分治+中序遍历优化

上面的两种方法都是先找到中间节点，再递归建立左右子树，属于先序遍历。这样，每次寻找中间节点时，就要logn的时间复杂度，总的时间复杂度变成了O(nlogn)。

如果我们可以用中序遍历，先建立左子树，左子树建完再建根，然后再建右子树，那么就省去了查找中间节点的时间，时间复杂度就变成了O(n)。

也就是说，我们没有必要“先”找到中间节点：我们可以先构建了左子树，建立结束后，指针自然指向中间结点。那么如何构建左子树呢？其实我们只需要确定子树的大小就可以。所以先用O(n)的时间计算链表长度，之后用中序遍历。当然，指针需要是“引用”，这样才能改变指针的指向，实现建好左子树后，指针自然指向中间结点。

下面是官方题解：

class Solution {
public:
    int getLength(ListNode* head) {
        int ret = 0;
        for (; head != nullptr; ++ret, head = head->next);
        return ret;
    }

    TreeNode* buildTree(ListNode*& head, int left, int right) {
        if(left>right) return NULL;
        int mid=(left+right)/2;
        TreeNode *root=new TreeNode();
        root->left=buildTree(head,left,mid-1);
        root->val=head->val;
        head=head->next;
        root->right=buildTree(head,mid+1,right);
        return root;
    }

    TreeNode* sortedListToBST(ListNode* head) {
        int length = getLength(head);
        return buildTree(head, 0, length - 1);
    }
};

时间复杂度：O(n)，其中 n 是链表的长度。

设长度为 n 的链表构造二叉搜索树的时间为 T(n)，递推式为 T(n)=2⋅T(n/2)+O(1)，根据主定理，T(n)=O(n)。

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