Java 1ms solution. Easy understood. The main idea of the solution is similar to merge sort.


  • 7
    J
    //The main idea of the solution is similar to merge sort.(#148 Sort List https://leetcode.com/problems/sort-list/) 
     //Divide the sorted list into halves. 
     //The middle of the list is root. 
     //The left half of the list is the left child of root. 
     //The right half of the list is the right child of root. 
     //Then do the same to the left child and right child recursively. 
     //Pay attention to the type: ListNode TreeNode
    public class Solution {
        public TreeNode sortedListToBST(ListNode head) {
            if(head==null){
                return null;
            }
            if(head.next==null){
                TreeNode treeNode=new TreeNode(head.val);
                return treeNode;
            }
            ListNode slow=head;
            ListNode fast=head.next.next;
            while(fast!=null&&fast.next!=null){
                slow=slow.next;
                fast=fast.next.next;
            }
            TreeNode root=new TreeNode(slow.next.val);
            ListNode temp=slow.next.next;
            slow.next=null;
            root.left=sortedListToBST(head);
            root.right=sortedListToBST(temp);
            return root;
        }
    }

Log in to reply
 

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