LeetCode 109. Convert Sorted List to Binary Search Tree [Medium] [C++] 解題筆記

Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

 

Example 1:

Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.

Example 2:

Input: head = []
Output: []

Example 3:

Input: head = [0]
Output: [0]

Example 4:

Input: head = [1,3]
Output: [3,1]

 

Constraints:

• The number of nodes in head is in the range [0, 2 * 104].
• -10^5 <= Node.val <= 10^5

想法:

    這題基本上和108. Convert Sorted Array to Binary Search Tree 一樣，只是資料結構改成 Linked-list，一樣使用類似 binary search 的技巧然後注意 linked-list的操作即可。

完整程式碼:

class Solution {

public:

    TreeNode* constructBST(ListNode* head) {

        if (head == nullptr) { return nullptr; }

        if (head->next == nullptr) { return new TreeNode(head->val); }

        ListNode* first = head;

        ListNode* second = head;

        ListNode* pre = new ListNode(0);

        pre->next = head;

        while (first != nullptr && first->next != nullptr) {

            first = first->next->next;

            second = second->next;

            pre = pre->next;

        }

        TreeNode* root = new TreeNode(second->val);

        pre->next = nullptr;

        root->left = constructBST(head);

        root->right = constructBST(second->next);

        return root;

    }

    TreeNode* sortedListToBST(ListNode* head) {

        return constructBST(head);

    }

};