Convert Sorted List to Binary Search Tree(C++ code)

LeetCode Convert Sorted Array to Binary Search Tree, Oct 2 '12

难度2，出现频率3

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
思路： 每次找中间位置的node，设为root,左孩子是左半边的根，右孩子是右半边的根。
tips:左半边并不是以NULL node结束的，写判断条件的时候要注意。

TreeNode *findroot(ListNode *head, ListNode *tail){

    if(head == NULL) return NULL;

    if(head == tail) {

       TreeNode *root = new TreeNode(head->val);

      root->left = NULL; root->right = NULL;

      return root;

    }

    ListNode *slow = head, *fast = head->next;

    while(fast != tail && fast->next != tail){
     
       slow = slow->next;

       fast = fast->next->next;

    }

    TreeNode *root = new TreeNode(slow->next->val);

    root->left = findroot(head, slow);

    if(slow->next == tail) root->right = NULL;
    else root->right = findroot(slow->next->next, tail);
return root;


}

TreeNode *sortedListToBST(ListNode *head) {

      if(head == NULL) return NULL;

      ListNode *tail = head;

      while(tail->next != NULL) tail = tail->next;

      return findroot(head, tail);     

   }