aboutsummaryrefslogtreecommitdiff
path: root/convert_sorted_bst.cpp
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;
  }
};