Java Solution Recursive without size


  • 0
    K

    public class Solution {

    public TreeNode sortedListToBST(ListNode head) {
        return bfs(head, null);
    }
    
    private TreeNode bfs(ListNode left, ListNode right) {
        if (left == null) return null;
        if (left == right) return new TreeNode(left.val);
        
        if (left.next == right) {
            TreeNode node = new TreeNode(left.val);
            if (right != null) node.right = new TreeNode(right.val);
            return node;
        }
        
        ListNode mid = left, fast = left, slow = left;
        while (fast != right) {
            fast = fast.next;
            if (fast != right) {
                slow = mid;
                mid = mid.next;
                fast = fast.next;
            }
        }
        TreeNode parent = new TreeNode(mid.val);
        parent.left = bfs(left, slow);
        parent.right = bfs(mid.next, right);
        return parent;
    }
    

    }


Log in to reply
 

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