Convert Sorted List to BST

Leave a comment

May 17, 2016 by oneOokay

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


基本上有两种想法:1.是找到中点recursively构建BST;2.用inorder traversal来做。

第一种:中点recursion:fast low指针找到中点;sortedListToBST本身作为recursion函数。但是由于fast slow指针while loop之后slow的位置,所以我们还需要slow之前的一个node,把node.next变成null,这样才能够进行下一次recursion。

时间复杂度为O(NlogN):每层递归一共访问N/2个节点,一共log N层递归(对应树的高度)。

Recursion:
public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = null;
        while (fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            pre = slow;//pre指针用来标记slow前一个node
            slow = slow.next;
        }
//slow作为root:slow为奇数nodes的中点或者偶数nodes的前半段末,
符合root
        TreeNode root = new TreeNode(slow.val);
//当fast和slow指针并没有移动的时候,pre为null
        if (pre != null)
            pre.next = null;
        else {//此时可知左子树为null
            head = null;
        }

        root.left = sortedListToBST(head);
        root.right = sortedListToBST(slow.next);
        return root;
    }
 

另一个由inorder从左子树开始逐渐build的方法很妙:

参考下面:TODO

http://articles.leetcode.com/convert-sorted-list-to-balanced-binary
http://bangbingsyb.blogspot.com/2014/11/leetcode-convert-sorted-list-to-binary.html
http://blog.csdn.net/worldwindjp/article/details/39722643

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

%d bloggers like this: