Convert Sorted List to Binary Search Tree Solutions in C++

// Source : https://oj.leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
// Author : Hao Chen
// Date   : 2014-07-03



#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <queue>
using namespace std;


struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};


struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


TreeNode* sortedListToBST(int low, int high, ListNode*& head);

TreeNode *sortedListToBST(ListNode *head) {
    int len = 0;
    
    for(ListNode* p=head; p!=NULL; p=p->next){
        len++;
    }
    return sortedListToBST(0, len-1, head);
}

TreeNode* sortedListToBST(int low, int high, ListNode*& head) {
    if (low>high || head==NULL) return NULL;

    int mid = low + (high - low)/2;

    TreeNode* leftNode = sortedListToBST(low, mid-1, head);

    TreeNode* node = new TreeNode(head->val);
    node->left = leftNode;
    head = head->next;

    TreeNode* rightNode = sortedListToBST(mid+1, high, head);
    node->right = rightNode;

    return node;
}

void printTree_level_order(TreeNode *root)
{
    queue<TreeNode*> q;
    q.push(root);
    while (q.size()>0){
        TreeNode* n = q.front();
        q.pop();
        if (n==NULL){
            cout << "# ";
            continue;
        }
        cout << n->val << " ";
        q.push(n->left);
        q.push(n->right);
    }
    cout << endl;
}

ListNode* createList(int a[], int n)
{
    ListNode *head=NULL, *p=NULL;
    for(int i=0; i<n; i++){
        if (head == NULL){
            head = p = new ListNode(a[i]);
        }else{
            p->next = new ListNode(a[i]);
            p = p->next;
        }
    }
    return head;
}

void printList(ListNode* h)
{
    while(h!=NULL){
        printf("%d -> ", h->val);
        h = h->next;
    }
    printf("NULL\n");
}


int main(int argc, char** argv)
{
    int n = 8;
    if (argc>1){
        n = atoi(argv[1]);
    }
    int *a = new int[n];
    for(int i=0; i<n; i++){
        a[i]=i+1;
    }
    ListNode* head = createList(a, n);
    printList(head);
    TreeNode* root = sortedListToBST(head); 
    printTree_level_order(root);
    delete[] a; 

    return 0;
}

#include <cstddef>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode *sortedListToBST(ListNode *head) {
        auto n = [](ListNode *p){
            int count{0};
            for ( ; p; p=p->next, ++count);
            return count;
        }(head);
        return sortedListToBST(&head, n);
    }
    TreeNode *sortedListToBST(ListNode **head_ref, int n) {
        if (n<1) return NULL;
        TreeNode *left = sortedListToBST(head_ref, n/2);
        TreeNode *root = new TreeNode((*head_ref)->val);
        root->left = left;
        *head_ref = (*head_ref)->next;
        root->right = sortedListToBST(head_ref, n-n/2-1);
        return root;
    } 
};

/// Source : https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/
/// Author : liuyubobobo
/// Time   : 2018-04-22

#include <iostream>

using namespace std;


/// 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) {}
};


/// Recursive
/// Time Complexity: O(nlogn)
/// Space Complexity: O(logn)
class Solution {

public:
    TreeNode* sortedListToBST(ListNode* head) {

        if(head == NULL)
            return NULL;

        int len = getLen(head);
        return buildBST(head, 0, len - 1);
    }

private:
    TreeNode* buildBST(ListNode* head, int l, int r){

        if(l > r)
            return NULL;

        if(l == r)
            return new TreeNode(head->val);

        int mid = l + (r - l + 1) / 2;
        ListNode* cur = head;
        for(int i = l ; i < mid - 1 ; i ++)
            cur = cur->next;

        ListNode* node = cur->next;
        cur->next = NULL;

        TreeNode* root = new TreeNode(node->val);
        root->left = buildBST(head, l, mid - 1);
        root->right = buildBST(node->next, mid + 1, r);
        return root;
    }

    int getLen(ListNode* head){

        ListNode* cur = head;
        int res = 0;
        while(cur != NULL){
            res ++;
            cur = cur->next;
        }
        return res;
    }
};


/// Test Helper
ListNode* createLinkedList(int arr[], int n){

    if(n == 0)
        return NULL;

    ListNode* head = new ListNode(arr[0]);
    ListNode* curNode = head;
    for(int i = 1 ; i < n ; i ++){
        curNode->next = new ListNode(arr[i]);
        curNode = curNode->next;
    }

    return head;
}

void inOrder(TreeNode* node){

    if(node == NULL)
        return;

    inOrder(node->left);
    cout << node->val << " ";
    inOrder(node->right);
}


int main() {

    int arr1[] = {-10, -3, 0, 5, 9};
    ListNode* head1 = createLinkedList(arr1, 5);
    inOrder(Solution().sortedListToBST(head1));
    cout << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/
/// Author : liuyubobobo
/// Time   : 2018-11-17

#include <iostream>

using namespace std;


/// 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) {}
};


/// Recursive and do the inorder simulation
/// Time Complexity: O(n)
/// Space Complexity: O(logn)
class Solution {

private:
    ListNode* cur;

public:
    TreeNode* sortedListToBST(ListNode* head) {

        if(head == NULL)
            return NULL;

        int len = getLen(head);
        cur = head;
        return buildBST(0, len - 1);
    }

private:
    TreeNode* buildBST(int l, int r){

        if(l > r)
            return NULL;

        int mid = l + (r - l + 1) / 2;
        TreeNode* left = buildBST(l, mid - 1);

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

        TreeNode* right = buildBST(mid + 1, r);

        root->left = left;
        root->right = right;
        return root;
    }

    int getLen(ListNode* head){

        ListNode* cur = head;
        int res = 0;
        while(cur != NULL){
            res ++;
            cur = cur->next;
        }
        return res;
    }
};


/// Test Helper
ListNode* createLinkedList(int arr[], int n){

    if(n == 0)
        return NULL;

    ListNode* head = new ListNode(arr[0]);
    ListNode* curNode = head;
    for(int i = 1 ; i < n ; i ++){
        curNode->next = new ListNode(arr[i]);
        curNode = curNode->next;
    }

    return head;
}

void inOrder(TreeNode* node){

    if(node == NULL)
        return;

    inOrder(node->left);
    cout << node->val << " ";
    inOrder(node->right);
}


int main() {

    int arr1[] = {-10, -3, 0, 5, 9};
    ListNode* head1 = createLinkedList(arr1, 5);
    inOrder(Solution().sortedListToBST(head1));
    cout << endl;

    return 0;
}