[LeetCode] 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.
Recursive
Time Complexity
O(nlogn)
Space Complexity
O(logn)
思路
Get the middle of the linked list and make it root.
Recursive do same for left half and right half.
It is the same way as convert sorted array to Binary Search Tree.
First we need to find the mid of the linked list. We can use slow and fast pointer.
The only difference is we can get the mid of the sorted array by just use nums[i]. But we need to search for linked list and need to find the previous node before mid.
Remember to break the linked list.
代码
public TreeNode sortedListToBST(ListNode head) {
//corner case & base case
if(head == null) return null;
if(head.next == null) return new TreeNode(head.val);
ListNode slow = head;
ListNode fast = head;
ListNode pre = null;
//find the pre list of mid
while(fast != null && fast.next != null){
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
pre.next = null;
TreeNode root = new TreeNode(slow.val);
root.left = sortedListToBST(head);
root.right = sortedListToBST(slow.next);
return root;
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论