Convert Sorted List to Binary Search Tree

ID: 109; medium

Solution 1 (Java)

``````/**
* 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 {
if (head == null) return null;
List<Integer> nums = new ArrayList<>();
}
return convert(nums, 0, nums.size() - 1);
}

private TreeNode convert(List<Integer> nums, int left, int right) {
if (left > right) return null;
int mid = left + (right - left) / 2;
TreeNode root = new TreeNode(nums.get(mid));
root.left = convert(nums, left, mid - 1);
root.right = convert(nums, mid + 1, right);
return root;
}
}``````

Solution 2 (Java)

``````/**
* 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 {
return null;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode rootNode = slow.next;
slow.next = null;

TreeNode root = new TreeNode(rootNode.val);
root.right = sortedListToBST(rootNode.next);
return root;
}
}``````

Notes

• Using the same idea, we find the middle node of the linked list. It is important to note that we find the previous node of the middle node first (`slow` when the while loop ends). The reasons is that we need to cut the connection between the previous node and the middle node.

• Time complexity: `O(n)`

• Space complexity: `O(1)`

Last updated