( “树” 之 BST) 109. 有序链表转换二叉搜索树 —

这篇具有很好参考价值的文章主要介绍了( “树” 之 BST) 109. 有序链表转换二叉搜索树 ——【Leetcode每日一题】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

二叉查找树（BST）：根节点大于等于左子树所有节点，小于等于右子树所有节点。
二叉查找树中序遍历有序。

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

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

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

示例 1:

( “树” 之 BST) 109. 有序链表转换二叉搜索树 ——【Leetcode每日一题】

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

示例 2:

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

提示:

head 中的节点数在 $0, 2 * 10^4]$ 范围内
$10^5 <= Node.val <= 10^5$

思路：分治 + 递归

法一：
先将链表转化为数组，具体思路为：108. 将有序数组转换为二叉搜索树

法二：快慢指针

和法一类似，我们使用快慢指针要找到有序链表的中位数，以该中位数为根节点，并将该中位数左右两边分成两个子有序链表，再在子有序链表找中位数，以此类推递归。

代码：(Java、C++)

法一：
Java

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        List<Integer> nums = new ArrayList<>();
        while(head != null){
            nums.add(head.val);
            head = head.next;
        }
        TreeNode root = toBST(nums, 0, nums.size() - 1);
        return root;
    }
    public TreeNode toBST(List<Integer> nums, int be, int ed){
        if(be > ed) return null;
        TreeNode root = new TreeNode(nums.get(be + (ed - be) / 2));
        root.left = toBST(nums, be, be + (ed - be) / 2 - 1);
        root.right = toBST(nums, be + (ed - be) / 2 + 1, ed);
        return root;
    }
}

C++

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        vector<int> nums;
        while(head != nullptr){
            nums.push_back(head->val);
            head = head->next;
        }
        TreeNode* root = toBST(nums, 0, nums.size() - 1);
        return root;
    }
    TreeNode* toBST(vector<int>& nums, int be, int ed){
        if(be > ed) return nullptr;
        TreeNode* root = new TreeNode(nums[be + (ed - be) / 2]);
        root->left = toBST(nums, be, be + (ed - be) / 2 - 1);
        root->right = toBST(nums, be + (ed - be) / 2 + 1, ed);
        return root;
    }
};

法二：快慢指针
Java

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        if(head.next == null) return new TreeNode(head.val);
        ListNode preMid = getPreMid(head);
        TreeNode root = new TreeNode(preMid.next.val);
        root.right = sortedListToBST(preMid.next.next);
        preMid.next = null;
        root.left = sortedListToBST(head);
        return root;
    }
    public ListNode getPreMid(ListNode head){
        ListNode slow = head;
        ListNode pre = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        return pre;
    }
}

C++

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if(head == nullptr) return nullptr;
        if(head->next == nullptr) return new TreeNode(head->val);
        ListNode* preMid = getPreMid(head);
        TreeNode* root = new TreeNode(preMid->next->val);
        root->right = sortedListToBST(preMid->next->next);
        preMid->next = nullptr;
        root->left = sortedListToBST(head);
        return root;
    }
    ListNode* getPreMid(ListNode* head){
        ListNode* slow = head;
        ListNode* pre = head;
        ListNode* fast = head;
        while(fast != nullptr && fast->next != nullptr){
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        return pre;
    }
};

运行结果：

( “树” 之 BST) 109. 有序链表转换二叉搜索树 ——【Leetcode每日一题】

复杂度分析：

时间复杂度： $O (n)$ ，其中 n 是链表的长度。
空间复杂度： $O (l o g n)$ ，法一为 $O (n)$ ，需要长度为n的数组；法二为 $O (n)$ ，这里只计算除了返回答案之外的空间。平衡二叉树的高度为 $O (l o g n)$ ，即为递归过程中栈的最大深度，也就是需要的空间。