Description
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
Given the sorted linked list: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
BST
Solution
DFS
首先找到list的中间节点，然后递归调用即可。递归的时候，要么把链表拆分成三部分，要么把tail节点传入，作为递归的终止条件。
把tail节点传入的写法更加简洁和直观，要记住哦！
/**
* 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;
}
return toBSTRecur(head, null);
}
// construct a BST using nodes between [head, tail)
public TreeNode toBSTRecur(ListNode head, ListNode tail) {
if (head == tail) {
return null;
}
ListNode slow = head;
ListNode fast = head;
while (fast != tail && fast.next != tail) {
fast = fast.next.next;
slow = slow.next;
}
TreeNode root = new TreeNode(slow.val);
root.left = toBSTRecur(head, slow);
root.right = toBSTRecur(slow.next, tail);
return root;
}
}
