leetcode Question 24: Convert Sorted List to Binary Search Tree

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Analysis:

The easier way to solve this problem is use the idea as the previous one.
Here present another way of thinking.
In the previous array to BST, we construct the BST in a top-down way. For the list data structure, to get the mid point every time is a waster of time. So construct the BST in a bottom-up way. However, the length of the list must be computed.

Recursively 
1. construct the left tree 
2. construct the root node, list pointer +1.
3. construct the right node

Note that in Python, the function argument is more like a "pass by value" way if the argument is immutable, to use the C++ like "pass by reference", the argument should be a mutable type, here in the code, a list of "ListNode" is used.

Code(C++):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    TreeNode *l2bst(ListNode* &head,int st, int ed){
        if (st>ed) {return NULL;}
        TreeNode *lefttree = l2bst(head,st,int(st+(ed-st)/2)-1);
        TreeNode *parent = new TreeNode(head->val); 
        head = head->next;
        TreeNode *righttree = l2bst(head,int(st+(ed-st)/2)+1,ed);
        parent->left  = lefttree;
        parent->right  = righttree;
        return parent;
    }
    
    TreeNode *sortedListToBST(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (head==NULL){return NULL;}
        ListNode *h=head;
        int len = 0;
        while (h){
            len = len+1;
            h = h->next;
        }
        TreeNode *root=l2bst(head,1,len);
        return root;

    }
};

Code(Python):

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a list node
    # @return a tree node
    def bst(self, head, st, ed):
        if st > ed or head[0] == None:
            return None
        mid = st + (ed - st)/2
        left = self.bst(head, st, mid - 1)
        root = TreeNode(head[0].val)
        head[0] = head[0].next
        right = self.bst(head, mid + 1, ed)
        root.left = left
        root.right = right
        return root

    def sortedListToBST(self, head):
        if head == None: 
            return None
        tmp = head
        n = 0
        while tmp != None:
            n += 1
            tmp = tmp.next
        return self.bst([head], 0, n)