/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null)
return null;
return dfs(head, null);
}
private TreeNode dfs(ListNode left, ListNode right) {
if (left == right)
return null;
ListNode slow = left;
ListNode fast = left;
while (fast != right && fast.next != right) {
fast = fast.next.next;
slow = slow.next;
}
TreeNode root = new TreeNode(slow.val);
// 这里是dfs(left, slow)是因为区间是[left, right)
root.left = dfs(left, slow);
root.right = dfs(slow.next, right);
return root;
}
}