Twenty Percent Knowledge

Sunday, July 17, 2016

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

Example

               2
1->2->3  =>   / \
             1   3

Could not imaging that I made it one pass! Yes!

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param head: The first node of linked list.
     * @return: a tree node
     */
    public TreeNode sortedListToBST(ListNode head) {  
        // write your code here
        if(head==null)return null;
        if(head.next==null)return new TreeNode(head.val);
        ListNode p1=head,p2=head,preP1=null;
        while(p2!=null&&p2.next!=null){
            preP1=p1;
            p1=p1.next;
            p2=p2.next.next;
        }//after this p1 is middle point
        preP1.next=null;//close left list
        ListNode left=head;
        TreeNode root = new TreeNode(p1.val);
        ListNode right = p1.next;
        root.left=sortedListToBST(left);
        root.right=sortedListToBST(right);
        return root;
    }
}
//I did not imagine to make this one pass, but CAO! I made it!
//Love BST with beautiful left and right and recursive programming

Sunday, July 17, 2016

No comments: