题目：
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
分析：
给定一个有序链表，将其转换为一个高度平衡的二叉搜索树。
首先遍历链表获得链表长度。之后通过递归生成二叉搜索树。其生成过程和树的中序遍历类型：先是左子树，然后是根节点，最后是右子树。每添加一个树节点，就把链表节点的值赋给树节点，然后指针指向下一个链表节点。
代码：
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
public class Solution { private ListNode listNode; public TreeNode sortedListToBST(ListNode head) { if(head == null) return null; int len = 0; ListNode p = head; while(p != null){ len++; p = p.next; } listNode = head; return generateBST(0, len - 1); } private TreeNode generateBST(int start, int end){ if(start > end) return null; int mid = (start + end) / 2; TreeNode leftNode = generateBST(start, mid - 1); TreeNode midNode = new TreeNode(listNode.val); listNode = listNode.next; TreeNode rightNode = generateBST(mid + 1, end); midNode.left = leftNode; midNode.right = rightNode; return midNode; } } |