blob: 8b5b656980179e4bceef7f28d2c04185a02d5f3f (
plain)
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
26
27
28
29
|
// 109. Convert Sorted List to Binary Search Tree
#include "leetcode.h"
/*
* given 'head' of a singly linked list where elements are sorted in ascending
* order convert it to a height balanced binary search tree. meaning the depth
* of two sub- trees of every node never differs by more than one.
*/
class Solution {
public:
TreeNode *sortedListToBST(ListNode *head) {
if (!head)
return NULL;
if (!head->next)
return new TreeNode(head->val);
auto slow = head, fast = head, pre = head;
while (fast && fast->next) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
pre->next = 0;
TreeNode *root = new TreeNode(slow->val);
root->left = sortedListToBST(head);
root->right = sortedListToBST(slow->next);
return root;
}
};
|