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.
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; }