package question;

/*
 @author: Roderland
 @create: 2020年08月16日---14:55
*/
public class Question109 {
 public static void main(String[] args) {
 //-10, -3, 0, 5, 9
 ListNode l1 = new ListNode(-10);
 ListNode l2 = new ListNode(-3);
 ListNode l3 = new ListNode(0);
 ListNode l4 = new ListNode(5);
 ListNode l5 = new ListNode(9);
 TreeNode treeNode = new Question109().sortedListToBST(l1);
 }
 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 (true) {
 if (fast.next==null||fast.next.next==null) break;
 fast=fast.next.next;
 pre=slow;
 slow=slow.next;
 }
 TreeNode root = new TreeNode(slow.val);
 if (pre!=null) {
 pre.next=null;
 root.left = sortedListToBST(head);
 }
 root.right = sortedListToBST(slow.next);
 return root;
 }
}

class ListNode {
 int val;
 ListNode next;
 ListNode(int x) { val = x; }

 public ListNode(int val, ListNode next) {
 this.val = val;
 this.next = next;
 }
}