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);
    }
}

No comments:

Post a Comment

Manacher's Longest Palindromic Substring Algorithm

http://manacher-viz.s3-website-us-east-1.amazonaws.com/#/