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;
    }
};




Related Posts

Intersection Of Two Linked Lists Problem

LeetCode 160. Given the heads of two singly linked-lists headA...

Sort List Problem

LeetCode 148. Given the head of a linked list, return...

Reorder List Problem

LeetCode 143. You are given the head of a singly...

Linked List Cycle Problem

LeetCode 141. Given head, the head of a linked list,...

Linked List Cycle II Problem

LeetCode 142. Given the head of a linked list, return...

Insertion Sort List Problem

LeetCode 147. Given the head of a singly linked list,...