Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Solution:
1. 找到midNode,这个就是root node
2. 两边建树 分别加到这个root的left, right
注意左右字数可能为null的情况 以及midNode可能为head的情况
public TreeNode sortedListToBST(ListNode head) { if (head == null) { return null; } ListNode mid = findMiddle(head); TreeNode root = new TreeNode(mid.val); ListNode midPost = mid.next; if (mid != head) { root.left = sortedListToBST(head); } root.right = sortedListToBST(midPost); return root; } public ListNode findMiddle(ListNode head) { if (head == null || head.next == null) { return head; } ListNode slow = head; ListNode fast = head.next; ListNode pre = null; while (fast != null && fast.next != null) { pre = slow; slow = slow.next; fast = fast.next.next; } //Remember to set pre.next = null if (pre != null) { pre.next = null; } return slow; }