Understand the problem:
As described in the problem, given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
This question is similar to the last post where a sorted array is changed to a sorted linked list. The mainly challenge is to find the mid point of the linked list. This can be easily done by using two pointers.
Solution:
The idea is still similar as the last post, where we were given a sorted array. So we first find the mid node of the linked list, partition to two lists, where the left list is the left subtree, and right part is the right subtree. We recursively repeat this process until the linked list become null.
Code (Java):
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; next = null; }
* }
*/
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
return toBST(head, null);
}
private TreeNode toBST(ListNode head, ListNode tail) {
if (head == tail) return null;
ListNode mid = findMid(head, tail);
TreeNode root = new TreeNode(mid.val);
root.left = toBST(head, mid);
root.right = toBST(mid.next, tail);
return root;
}
// Find the middle node of the linked list
private ListNode findMid(ListNode head, ListNode tail) {
ListNode slow = head;
ListNode fast = head;
while (fast != tail && fast.next != tail && fast.next.next != tail) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
Discussion:
Note that in the recursive function we used a tail pointer points to the tail of the partitioned linked list. That is unusual for a linked list because we usually only track the head node of the list. In this problem, since we need to know the tail of the list, one method is to truncate the linked list. However, this solution has several drawbacks. First of all, it need to modify the linked list, which may not be desirable in practice. More important, we need to traverse the linked list again until the node before the mid node. Then set the next to null. It DOES NOT work just setting mid as null. Consider why the following code is wrong:
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
return toBST(head);
}
private TreeNode toBST(ListNode head) {
if (head == null) return null;
ListNode mid = findMid(head);
TreeNode root = new TreeNode(mid.val);
// Terminate the left list
ListNode rHead = mid.next;
if (head == mid) {
head = null;
} else {
mid = null;
}
root.left = toBST(head);
root.right = toBST(rHead);
return root;
}
// Find the middle node of the linked list
private ListNode findMid(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
That is because just setting mid as null does not modify the linked list at all. It only modify the mid pointer but the linked list remains the same.
Now we analyze the complexity of this solution. Since finding the middle node takes O(n) time, the overall time complexity becomes O(n^2). The space complexity is O(logn).
A Better Solution:
Note that in the previous solution the cost is on finding the middle node of the linked list, which takes O(n) time on average. If we can construct the tree in the order that we traverse the linked list, we don't need to jump back and forth to find the middle of the list. Remember the inorder traversal of a binary tree, if it is a BST, the inorder traversal should be in ascending order. Can we do the reverse, i.e, given an sorted list, construct the BST inorder, i.e, from bottom-up? The answer is yes.
Code (Java):
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; next = null; }
* }
*/
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private ListNode p;
public TreeNode sortedListToBST(ListNode head) {
int len = getListLength(head);
p = head;
return toBST(0, len - 1);
}
private TreeNode toBST(int lo, int hi) {
if (lo > hi) return null;
int mid = (lo + hi)/2;
TreeNode left = toBST(lo, mid - 1);
TreeNode root = new TreeNode(p.val);
p = p.next;
TreeNode right = toBST(mid + 1, hi);
root.left = left;
root.right = right;
return root;
}
private int getListLength(ListNode head) {
ListNode p = head;
int length = 0;
while (p != null) {
p = p.next;
length++;
}
return length;
}
}
Discussion:
Now the time complexity becomes O(n) since we traverse the linked list in order.
Summary:
This post we learned how to convert a linked list to a BST. Note the linked list has no constant time in accessing a node, so we must build the tree from bottom up. Why we choose to traverse the tree in order, because the array is sorted and the inorder traversal can generate a BST.
Update on 10/7/14:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; next = null; }
* }
*/
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
return toBSTHelper(head);
}
private TreeNode toBSTHelper(ListNode head) {
if (head == null) {
return null;
}
if (head.next == null) {
return new TreeNode(head.val);
}
// Find middle minus one node of the linked list
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null && fast.next.next != null && fast.next.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode mid = slow.next;
TreeNode root = new TreeNode(mid.val);
slow.next = null;
root.left = toBSTHelper(head);
root.right = toBSTHelper(mid.next);
return root;
}
}
No comments:
Post a Comment