Convert Sorted List to Binary Search Tree,Leetcode 解题笔记

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

跟上一题类似,不过把array换成了list,没有了random access的方便,如果还是同样的思路,每次都要找到中点,很费时间。
巧妙的方法是bottom up,从底向上建树,这样只需要扫描一遍list就把树建成了。
(网上所有的解释都是很简单的说了bottom up,但是这里我只理解了思路,具体实现时这个树是怎么递归建成的一直没想清楚,也找不到更清晰的说明,可能其他人都觉得太简单不屑于讨论了吧。)

/**
 * 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 {
    ListNode h;
    public TreeNode sortedListToBST(ListNode head) {
        int len = getLength(head);
        h = head;
        return convert(0, len-1);
    }
    
    public int getLength(ListNode head){
        int len = 0;
        ListNode newhead = head;
        while(newhead != null){
            newhead = newhead.next;
            len++;
        }
        return len;
    }
    
    public TreeNode convert(int start, int end){
        if(start > end) return null;
        int mid = (start + end) / 2;
        TreeNode left = convert(start, mid-1);
        TreeNode root = new TreeNode(h.val);
        h = h.next;
        TreeNode right = convert(mid+1, end);
        root.left = left;
        root.right = right;
        return root;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s