109. Convert Sorted List to Binary Search Tree (Java Solution)


  • 0
    T
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public TreeNode sortedListToBST(ListNode head) {
          if (head == null) {
          	return null;
          }
          
          int len = len(head);
          
          if (len == 1) {
          	return new TreeNode(head.val);
          }
          
          ListNode justBeforeMiddle = head;
          
          for (int i=0; i < len/2 -1; i++) justBeforeMiddle = justBeforeMiddle.next;
          
          ListNode middle = justBeforeMiddle.next;
          justBeforeMiddle.next = null;
          
          
          TreeNode root = new TreeNode(middle.val);
          
          root.left = sortedListToBST(head);
          root.right = sortedListToBST(middle.next);
          
          return root;
        }
            
        public int len(ListNode head) {
          if (head == null) {
            return null;
          }
          return 1 + len(head.next);
        }
    }
    
    

Log in to reply
 

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