Friday, February 7, 2014

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.

Solution:
bottom up!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 

/**

public class Solution {
    ListNode h = null;
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        h = head;
        int len = getLen(head);
        return buildBST(0, len-1);
    }
    
    public TreeNode buildBST(int begin, int end){
        if(begin > end)
            return null;
        int mid = (begin + end) / 2;
        
        TreeNode left = buildBST(begin, mid - 1);
        TreeNode root = new TreeNode(h.val);
        h = h.next;
        TreeNode right = buildBST(mid + 1, end);
        
        root.left = left;
        root.right = right;
        return root;
    }
    
    public int getLen(ListNode head){
        int len = 0;
        while(head != null){
            len++;
            head = head.next;
        }
        return len;
    }
}

No comments:

Post a Comment