109 Convert Sorted List to Binary Search Tree
ref 109. 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.
Company tag: Zenefit
分析
有点没有完全想明白。
能够理解的点有：
给你一个sorted list，用这里面的树构建bst，说明这个list是该bst的inorder遍历。
给你的list相当于一个queue，每次用掉一个node就往后移动一格，相当于queue.poll();
和之前那题serialize的题有点像，我当时选择的方式是preorder，这里是Inorder。但是那个里面叶节点会用#标记，这里没有#, 只能用一个start, end来标记，如果start>end那么就说明已经到叶节点了，返回空，所以建树的顺序是 left = 递归()=> 创建root => root.left = left => root.right = 递归另一半
代码
private ListNode node;
public TreeNode sortedListToBST(ListNode head) {
if(head == null) {
return null;
}
int size = 0;
node = head;
ListNode cur = head;
while(cur != null) {
cur = cur.next;
size++;
}
return constructTree(0, size - 1);
}
private TreeNode constructTree(int start, int end) {
if(start > end) {
return null;
}
int mid = start + (end - start) / 2;
TreeNode left = constructTree(start, mid - 1);
TreeNode root = new TreeNode(node.val);
root.left = left;
node = node.next;
root.right = constructTree(mid + 1, end);
return root;
}
我觉得时间复杂度是O(n)，因为node只走了一遍。
可以把serialize和deserialize用inorder再做一遍