Leetcode Convert Sorted List to Binary Search Tree problem solution

YASH PAL,

In this Leetcode Convert Sorted List to Binary Search Tree problem solution we have Given the head of a singly linked list where elements are sorted in ascending order, convert to a height-balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than 1.

Leetcode Convert Sorted List to Binary Search Tree problem solution

Problem solution in Python.

def sortedListToBST(self, head):
        if not head: return None
        return self.DFS(head)
       
    def DFS(self, head):
	
        if not head: 
            return None

        if not head.next:
            return TreeNode(head.val)
        prev, slow, fast = None, head, head
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next
            
        tmp = prev.next
        prev.next = None
        node = TreeNode(slow.val)
        node.left = self.DFS(head)
        node.right = self.DFS(slow.next)
        return node

Problem solution in Java.

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head==null)
            return null;
        else
            return BST(head,null);
    }
    public static TreeNode BST(ListNode head,ListNode tail){
        ListNode slow=head;
        ListNode fast=head;
        if(head==tail)
            return null;
        while(fast!=tail&&fast.next!=tail){
            slow=slow.next;
            fast=fast.next.next;
        }
        TreeNode root=new TreeNode(slow.val);
        root.left=BST(head,slow);
        root.right=BST(slow.next,tail);
        return root;
    }
}

Problem solution in C++.

class Solution {
public:
    
    
    TreeNode* sortedListToBST(ListNode* head) {
        if(!head)
            return NULL;
        ListNode *slow=head;
        ListNode *fast=head->next,*tt=NULL;
        while(fast and fast->next)
        {
            tt=slow;
            slow=slow->next;
            fast=fast->next->next;
        }
        if(tt)
            tt->next=NULL;
        else 
            head=NULL;
        
        TreeNode *curr=new TreeNode(slow->val);
        TreeNode *r=sortedListToBST(slow->next);
        TreeNode *l=sortedListToBST(head);
        curr->left=l;curr->right=r;
        return curr;
    }
};

Problem solution in C.

struct TreeNode* get(int v){
		struct TreeNode* x;
		x=(struct TreeNode*)malloc(sizeof(struct TreeNode));
		x->val=v;
		x->left=NULL;
		x->right=NULL;
		return x;
}
struct TreeNode* func(int *b,int l,int h){
		struct TreeNode* root;
		int m=(l+h)/2;   
		if(h>=l){
			root=get(b[m]);
			root->left=func(b,l,m-1);
			root->right=func(b,m+1,h);
			return root;
		}
		else
			return NULL;
}

struct TreeNode* sortedListToBST(struct ListNode* head){
		struct TreeNode* t;
		int a=pow(10,4);
		int b[2*a];
		int i=0,j;
		while(head!=NULL){
			b[i]=head->val;
			head=head->next;
			i++;
		}
		int l=0,h=i-1;
		t=func(b,l,h);
		return t;
}

coding problems