Leetcode 109 Solution

This article provides solution to leetcode question 109 (convert-sorted-list-to-binary-search-tree)

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree

Solution

``````/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head, int cnt) {
if (head == NULL || cnt == 0)
return NULL;

ListNode* p1 = head;

for (int i = 0; i < cnt / 2; i++)
{
p1 = p1->next;
}

TreeNode* node = new TreeNode(p1->val);
node->left = sortedListToBST(head, cnt / 2);
node->right = sortedListToBST(p1->next, cnt - cnt / 2 - 1);

return node;
}

TreeNode* sortedListToBST(ListNode* head) {
ListNode* p = head;

int cnt = 0;

while (p)
{
p = p->next;
cnt++;
}