109.有序链表转换二叉搜索树 (Medium)*

题目描述*

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

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

示例*

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

代码*

可以先用数组存链表，然后用 108 题的算法，每次选取中间点作为根结点。或者使用快慢指针找到中间点。

还可以按照中序遍历的顺序赋值。

转换为数组快慢指针线性时间

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

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

class Solution {
private:
    ListNode *cur = nullptr;
public:
    TreeNode* sortedListToBST(ListNode* head) {
        cur = head;
        int end = 0;
        while(head != nullptr) {
            end++;
            head = head->next;
        }
        return helper(0, end);
    }
    TreeNode* helper(int start, int end) {
        if(start == end) {
            return nullptr;
        }
        int mid = start + (end - start) / 2;
        // 遍历左子树且返回根结点
        TreeNode *left = helper(start, mid);
        // 赋值当前根结点
        TreeNode *root = new TreeNode(cur->val);
        root->left = left;
        cur = cur->next;
        // 遍历右子树且返回根结点
        TreeNode *right = helper(mid + 1, end);
        root->right = right;
        return root; 
    }
};

最后更新: July 23, 2022