109. 有序链表转换二叉搜索树

发布时间 2024-01-04 16:25:47作者: MarkLeeBYR

和题目108类似:108是数组  https://www.cnblogs.com/MarkLeeBYR/p/16906818.html

public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
return helper(head, null);
}
private TreeNode helper(ListNode head, ListNode tail){
if (head == tail) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while (fast != tail && fast.next != tail) {
fast = fast.next.next;
slow = slow.next;
}
TreeNode root = new TreeNode(slow.val);
root.left = helper(head, slow);
root.right = helper(slow.next, tail);
return root;
}