题意：给定一个拍序的list，把它转为二叉搜索树
思路：
- 用runner记录当前遍历过的list节点
- 统计list节点个数
- 递归的把节点转换为二叉搜索树，具体见代码
思想：树的中序遍历
复杂度：时间O（n)，空间O(n)
class Solution {
ListNode runner;
public TreeNode sortedListToBST(ListNode head) {
if(head == null)
return null;
int len = 0;
ListNode temp = head;
while(temp != null) {
temp = temp.next;
len++;
}
runner = head;
return build(0, len - 1);
}
// 用start和end记录当前节点的左右边界
TreeNode build(int start, int end) {
if(start > end)
return null;
// 获取中间的节点
int m = (end - start)/2 + start;
// 中间节点左边的点都是左子树
TreeNode left = build(start, m - 1);
// 获取当前节点并前移runner
TreeNode cur = new TreeNode(runner.val);
cur.left = left;
runner = runner.next;
// 中间节点的右边都是右子树
TreeNode right = build(m + 1, end);
cur.right = right;
return cur;
}
}
