My ac code use two pionter to find mid,then recurisive convert to bst


  • 0
    T
    public TreeNode sortedListToBST(ListNode head) {
    	
    	if (head == null){
    		return null;
    	}
    	ListNode fast = head;
    	ListNode prev = null;
    	ListNode slow = head;
    	while (fast != null && fast.next != null) {
    		fast = fast.next.next;
    		prev = slow;
    		slow = slow.next;
    	}
    	TreeNode root = new TreeNode(slow.val);
    	if (prev != null){//important
    		prev.next = null;
    	}else{
    		head = null;
    	}
    	root.left = sortedListToBST(head);
    	root.right = sortedListToBST(slow.next);
    	return root;
    }

  • 0
    T

    // 1. choose the middle one as root,two poniter
    // 2. build left sub BST
    // 3. build right sub BST
    // 4. do this recursively.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.