Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
把一个有序链表转化为平衡二叉树。
思路：利用快慢指针找到中间节点，这也就是根节点，然后递归调用生成平衡二叉树函数分别生成根节点的左右节点。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; next = null; } * } */ /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode sortedListToBST(ListNode head) { if(head == null) return null; ListNode fast = head; ListNode slow = head; ListNode temp = null; while(fast != null && fast.next != null) { fast = fast.next.next; temp = slow; slow = slow.next; } if(temp == null) { head = null; }else{ temp.next = null; } //上面几行代码必须加，不加报索引越界错误。 TreeNode root = new TreeNode(slow.val); root.left = sortedListToBST(head); root.right = sortedListToBST(slow.next); return root; } }
