( “树” 之 BST) 109. 有序链表转换二叉搜索树 ——【Leetcode每日一题】网站首页 学无止境

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

期望上岸的鱼 2023-06-04 20:00:02

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

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

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

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

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

示例 1:

在这里插入图片描述

输入: 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;
    }
};

运行结果：

在这里插入图片描述

复杂度分析：

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