Convert sorted list to binary search tree | Leetcode 109

Solution

1) 0:00 Explaining the problem out loud
2) 1:10 Algorithm walkthrough
3) 2:30 Solution for Convert Sorted array to BST
3) 7:15 Coding it up
4) 10:00 Time Complexity

PS : Please increase the speed to 1.25X

[sawanpatel]

Let me like this video, , ...let me comment on this me tell you thank

[PujaKumari-zlrw]

Thank you for such an easy explanation :)

[HenggaoCai]

The method signature of this problem is different. In the actual problem that I see, we are passing a ListNode head as a argument for SortedArrayBST.

[santoshvarma]

can you please also explain the time and space complexity of this problem?

[HenggaoCai]

My Solution:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if(head == null) {
return null;
}

TreeNode
return root;
}

private TreeNode head){
if(head == null){
return null;
}

if(head.next == null){
TreeNode x=new TreeNode(head.val);
x.left=null;
x.right=null;
return x;
}

ListNode fast=head;
ListNode slow=head;
ListNode parent=slow;

while(slow != null && fast != null && fast.next != null){
fast=fast.next.next;
parent=slow;
slow=slow.next;
}

ListNode rightHead=slow.next;
parent.next=null;

TreeNode root=new TreeNode(slow.val);



return root;
}
}

[shyamsundar]

Are you planning to make a discord server ?