Wednesday, March 20, 2013
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.
/**
* 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; }
* }
*/
Recursively build the tree.
public class Solution {
TreeNode sortToBST(ListNode[] list, int start, int end){
if(start > end) return null;
int mid = (start + end) / 2;
TreeNode leftchild = sortToBST(list, start, mid-1);
TreeNode parent = new TreeNode(list[0].val);
parent.left = leftchild;
list[0] = list[0].next;
parent.right = sortToBST(list,mid+1, end);
return parent;
}
public TreeNode sortedListToBST(ListNode head) {
// Start typing your Java solution below
// DO NOT write main() function
ListNode[] l = new ListNode[1];
l[0] = head;
int len = 0;
while(head!=null){
len ++; head = head.next;
}
return sortToBST(l,0,len-1);
}
}
Subscribe to:
Post Comments (Atom)
Manacher's Longest Palindromic Substring Algorithm
http://manacher-viz.s3-website-us-east-1.amazonaws.com/#/
-
Suppose a bus is running on a loop route. It takes 10 mins for the bus to finish the route. If a guy arrives at a bus stop at uniformly rand...
-
Question: You are playing a card game with me. Suppose I shuffle a deck of 52 cards, then I show you the card one by one to you from top t...
-
Move Objects There are N objects kept in a row. The ith object is at position x_i. You want to partition them into K groups. You want ...
No comments:
Post a Comment