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
headis in the range[0, 2 * 104]. -105 <= Node.val <= 105
Solution 1: Recursion w/ Fast + Slow Pointers
For each sublist, use fast/slow pointers to find the mid and build the tree.
Time complexity: O(nlogn)
Space complexity: O(logn)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public: TreeNode *sortedListToBST(ListNode *head) { function<TreeNode*(ListNode*, ListNode*)> build = [&](ListNode* head, ListNode* tail) -> TreeNode* { if (!head || 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 = build(head, slow); root->right = build(slow->next, tail); return root; }; return build(head, nullptr); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment