Convert Sorted List To Binary Search Tree Problem
Description
LeetCode Problem 109.
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:
1
2
3
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:
1
2
Input: head = []
Output: []
Example 3:
1
2
Input: head = [0]
Output: [0]
Example 4:
1
2
Input: head = [1,3]
Output: [3,1]
Constraints:
- The number of nodes in head is in the range [0, 2 * 10^4].
- -10^5 <= Node.val <= 10^5
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
TreeNode *sortedListToBST(ListNode *head) {
return sortedListToBST( head, NULL );
}
private:
TreeNode *sortedListToBST(ListNode *head, ListNode *tail) {
if( head == tail )
return NULL;
if( head->next == tail ) {
TreeNode *root = new TreeNode( head->val );
return root;
}
ListNode *mid = head, *temp = head;
while( temp != tail && temp->next != tail ) {
mid = mid->next;
temp = temp->next->next;
}
TreeNode *root = new TreeNode( mid->val );
root->left = sortedListToBST( head, mid );
root->right = sortedListToBST( mid->next, tail );
return root;
}
};