Java Recursive with detailed explanation


  • 0

    1 Use three pointer: fast, slow, pre to find the middle point of list.
    2 Create new TreeNode root with the value of middle point.
    3 If pre!=null root has left child. So we create left child by using the list between head and middle point.
    4 Create right child by using the list after middle point.

    public class Solution {
        public TreeNode sortedListToBST(ListNode head) {
            if(head==null)
                return null;
            if(head.next==null)
                return new TreeNode(head.val);
            ListNode fast=head;
            ListNode slow=head;
            ListNode pre=null;
            while(fast.next!=null && fast.next.next!=null){
                fast=fast.next.next;
                pre=slow;
                slow=slow.next;
            }
            ListNode r = slow;
            TreeNode root=new TreeNode(r.val);
            
            if(pre!=null){
                pre.next=null;
                root.left=sortedListToBST(head);
            }
            ListNode right = r.next;
            r.next=null;
            root.right=sortedListToBST(right);
            return root;
        }
    }

Log in to reply
 

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