ConvertSortedListToBinarySearchTree [source code]
public class ConvertSortedListToBinarySearchTree {
static
/******************************************************************************/
class Solution {
public TreeNode sortedListToBST(ListNode head) {
List<Integer> nodes = new ArrayList<> ();
while (head != null) {
nodes.add (head.val);
head = head.next;
}
int N = nodes.size ();
return build (nodes, 0, N - 1);
}
TreeNode build (List<Integer> nodes, int lo, int hi) {
if (lo > hi)
return null;
int mid = lo + (hi + 1 - lo - 1) / 2;
TreeNode res = new TreeNode (nodes.get (mid));
res.left = build (nodes, lo, mid - 1);
res.right = build (nodes, mid + 1, hi);
return res;
}
}
/******************************************************************************/
public static void main(String[] args) {
ConvertSortedListToBinarySearchTree.Solution tester = new ConvertSortedListToBinarySearchTree.Solution();
}
}
感觉这题又给divide&conquer还有returned recursion这些思路有关系;
root level decision的动作估计跟这个balance有一定的关系;
这题为什么输入要给一个LinkedList? 能不能先全都放到一个array里面去? divide&conquer这种需要大量index操作的, 感觉用LinkedList很姜;
反正也没说不行, 我就先这样写算了;
想到一个问题, 如果两个tree height差距上限是1, 那么他们size差距是多少? 实际上, 是没有保证的; 最多两者的size可以差两倍; 所以感觉这题直接用等分的思路来做是不是会有点naive?
不过因为是sorted, 所以等分应该也不会出问题, 左边的subarray组成的subtree肯定跟右边的subarray组成的subtree有正确的大小关系;
等分可能是一个充分的手段, 但是不是必要的, 好像可以这样理解;
另外, 不能反过来说: 只要两个tree的size不超过两倍关系, 那么height差距就不会超过1, 这个逻辑的推理关系有问题;
最后很轻松的就AC了, 速度是5ms (2%); 看来真的是只要找到一个充分条件就行了;
注意这里的base case是用的leaf位置返回Null; 这个好像以前见到过; BST问题里面用pre leaf来控制base case好像有点麻烦; 特指returned recursion的时候; mutation recursion的时候还没有总结过;
没有editorial;
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
if(head==null) return null;
return toBST(head,null);
}
public TreeNode toBST(ListNode head, ListNode tail){
ListNode slow = head;
ListNode fast = head;
if(head==tail) return null;
while(fast!=tail&&fast.next!=tail){
fast = fast.next.next;
slow = slow.next;
}
TreeNode thead = new TreeNode(slow.val);
thead.left = toBST(head,slow);
thead.right = toBST(slow.next,tail);
return thead;
}
}
看起来很厉害, 然而:
The time complexity of the solution is O(n logn) since you have to traverse the sub-list in each recursive call.
这个复杂度的分析并不trivial, 脑子里要有一个visual, 才能aggregate出来, 每一个level用于traversal(其实也就是subproblem的sublist的长度之和)就是N;
private ListNode node;
public TreeNode sortedListToBST(ListNode head) {
if(head == null){
return null;
}
int size = 0;
ListNode runner = head;
node = head;
while(runner != null){
runner = runner.next;
size ++;
}
return inorderHelper(0, size - 1);
}
public TreeNode inorderHelper(int start, int end){
if(start > end){
return null;
}
int mid = start + (end - start) / 2;
TreeNode left = inorderHelper(start, mid - 1);
TreeNode treenode = new TreeNode(node.val);
treenode.left = left;
node = node.next;
TreeNode right = inorderHelper(mid + 1, end);
treenode.right = right;
return treenode;
}
大概理解了意思, 这个算法还真的是比较聪明的, 而且应该是这个题目真正想要看到的答案: 对list只需要一个traversal;
这个思路的核心是, 如果我们知道一个subarray对应一个subtree, 那么实际上最后: [left subtree's subarray] root [right subtree's subarray]这个是一个InOrder的排列; 实际上, 这个list就是一个InOrder traversal; 我们从Bottom-Up的过程建立这个BST的过程, 实际上最后走的就是一个InOrder traversal, 正好对应上了list的index顺序;
感觉讲的还是不够准确;
Hi! Just a little confusion here. Your solution should be O(n), but it doesn’t run consistently faster than my O(nlgn) solution. Any thoughts on the reason? Awesome solution btw:)
public TreeNode sortedListToBST(ListNode head) {
// base case
if (head == null) return null;
ListNode slow = head;
ListNode fast = head;
ListNode prev = null;
// find the median node in the linked list, after executing this loop
// fast will pointing to the last node, while slow is the median node.
while (fast.next != null) {
fast = fast.next;
if (fast.next == null) {
break;
}
fast = fast.next;
prev = slow;
slow = slow.next;
}
if (prev != null) prev.next = null;
else head = null;
TreeNode root = new TreeNode(slow.val);
root.left = sortedListToBST(head);
root.right = sortedListToBST(slow.next);
return root;
}
这个人是意识到了一部分的insight, 但是没有完全参透; 他这里看透的一点就是, 每一个subarray只要维护一个head就行了, 这也是为什么这题给你出LinkedList的input的可能性; 这个思路在之前两道construct BST from traversals的题目里面也见到过了;
他没有意识到的是整个recursion Bottom-Up的过程, 就是一个InOrder traversal的顺序;
有人认为他这个不算是O(1)空间, 因为recursion Stack:
Thanks for you reminder. I think usually we discuss the space complexity is based on heap space rather than stack space.
我也要能够做出这样的回应;
Here is similar solution where list state is stored in a parameter instead of a field which I believe makes it a thread safe implementation:
public class Solution {
private static class State {
ListNode head;
State(ListNode head) {
this.head = head;
}
}
public TreeNode sortedListToBST(ListNode head) {
return sortedListToBST(size(head), new State(head));
}
private TreeNode sortedListToBST(int size, State state) {
if (size<=0) return null;
int mid = size/2;
TreeNode root = new TreeNode(0);
root.left = sortedListToBST(mid, state);
root.val = state.head.val;
state.head = state.head.next;
root.right = sortedListToBST(size - mid - 1, state);
return root;
}
private int size(ListNode head) {
int size = 0;
while (head != null) {
head = head.next;
size++;
}
return size;
}
}
你说是就是吧;
count is a function to calculate the size of list.
Key words: inorder traversal.
class Solution {
public:
ListNode *list;
int count(ListNode *node){
int size = 0;
while (node) {
++size;
node = node->next;
}
return size;
}
TreeNode *generate(int n){
if (n == 0)
return NULL;
TreeNode *node = new TreeNode(0);
node->left = generate(n / 2);
node->val = list->val;
list = list->next;
node->right = generate(n - n / 2 - 1);
return node;
}
TreeNode *sortedListToBST(ListNode *head) {
this->list = head;
return generate(count(head));
}
};
跟上面那个其实是类似的;
Good point. I’ve seen too many people in this forum claiming their recursive solution to take O(1) space.
As a rule of thumb, a recursive program almost NEVER has O(1) space complexity:)
以后, 直接写O(1) heap space就行了;
article
If you have not checked out my previous post: Convert Sorted Array to Balanced Binary Search Tree (BST), you should check it out now as this solution is built upon the previous solution.
Things get a little more complicated when you have a singly linked list instead of an array. Please note that in linked list, you no longer have random access to an element in O(1) time.
所以我自己一开始这个全部丢到list里面的做法肯定是不行的; 真正面试的时候不带这样避开问题核心的; 最差最差的, 要能想到他们这种快慢指针的NlogN的做法;
Singly-linked lists contain nodes which have a data field as well as a next field, which points to the next node in the linked list.
Naive Solution:
A naive way is to apply the previous solution directly. In each recursive call, you would have to traverse half of the list’s length to find the middle element. The run time complexity is clearly O(N lg N), where N is the total number of elements in the list. This is because each level of recursive call requires a total of N/2 traversal steps in the list, and there are a total of lg N number of levels (ie, the height of the balanced tree).Hint:
How about inserting nodes following the list’s order? If we can achieve this, we no longer need to find the middle element, as we are able to traverse the list while inserting nodes to the tree.Best Solution:
As usual, the best solution requires you to think from another perspective. In other words, we no longer create nodes in the tree using the top-down approach. We create nodes bottom-up, and assign them to its parents. The bottom-up approach enables us to access the list in its order while creating nodes.Isn’t the bottom-up approach neat? Each time you are stucked with the top-down approach, give bottom-up a try. Although bottom-up approach is not the most natural way we think, it is extremely helpful in some cases. However, you should prefer top-down instead of bottom-up in general, since the latter is more difficult to verify in correctness.
他虽然说是Bottom-Up, 我认为这题其实还是理解了DFS InOrder本身执行顺序的一个order的核心;
Below is the code for converting a singly linked list to a balanced BST. Please note that the algorithm requires the list’s length to be passed in as the function’s parameters. The list’s length could be found in O(N) time by traversing the entire list’s once. The recursive calls traverse the list and create tree’s nodes by the list’s order, which also takes O(N) time. Therefore, the overall run time complexity is still O(N).
BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {
if (start > end) return NULL;
// same as (start+end)/2, avoids overflow
int mid = start + (end - start) / 2;
BinaryTree *leftChild = sortedListToBST(list, start, mid-1);
BinaryTree *parent = new BinaryTree(list->data);
parent->left = leftChild;
list = list->next;
parent->right = sortedListToBST(list, mid+1, end);
return parent;
}
BinaryTree* sortedListToBST(ListNode *head, int n) {
return sortedListToBST(head, 0, n-1);
}
public TreeNode sortedListToBST(ListNode head) {
if(head == null)
return null;
ListNode fast = head;
ListNode slow = head;
ListNode prev =null;
while(fast != null && fast.next != null)
{
fast = fast.next.next;
prev =slow;
slow=slow.next;
}
TreeNode root = new TreeNode(slow.val);
if(prev != null)
prev.next = null;
else
head = null;
root.left = sortedListToBST(head);
root.right = sortedListToBST(slow.next);
return root;
}
Traverse the list to get the middle element and make that the root. left side of the list forms left sub-tree and right side of the middle element forms the right sub-tree.
这个就是希望你保底能想出来的解法, 核心insight是每一个subtree的sublist只需要左边的head就够了;
好像这个insight其实也不是那么trivial的;
submission最优解: 1(46):
class Solution {
private ListNode current;
private int getSize(ListNode head){
int size = 0;
while(head != null){
size++;
head = head.next;
}
return size;
}
private TreeNode sortedListToBSTHelper(int size){
if (size <= 0){
return null;
}
TreeNode left = sortedListToBSTHelper(size / 2);
TreeNode root = new TreeNode(current.val);
current = current.next;
TreeNode right = sortedListToBSTHelper(size - size / 2 - 1);
root.left = left;
root.right = right;
return root;
}
public TreeNode sortedListToBST(ListNode head) {
if (head == null){
return null;
}
current = head;
int size = getSize(head);
return sortedListToBSTHelper(size);
}
}
就是O(N)的做法;
Problem Description
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
Given the sorted linked list: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/ \
-3 9
/ /
-10 5
Difficulty:Medium
Total Accepted:126.3K
Total Submissions:358K
Contributor:LeetCode
Companies
zenefits
Related Topics
linked listdepth-first search
Similar Questions
Convert Sorted Array to Binary Search Tree