Convert Sorted List to Balanced BST
思路:
用merge sort的思想来做很简单,时间复杂度是O(nlogn)。因为没一次递归都要遍历链表找中点。
另一种是inorder traversal, 实在是太巧妙了,估计面试的时候想不出来。
实现:
关于找中点slow和fast初始化问题, fast = head or fast = head.next对于最后结果并没有什么影响。
用merge sort的思想来做很简单,时间复杂度是O(nlogn)。因为没一次递归都要遍历链表找中点。
另一种是inorder traversal, 实在是太巧妙了,估计面试的时候想不出来。
实现:
关于找中点slow和fast初始化问题, fast = head or fast = head.next对于最后结果并没有什么影响。
评论
发表评论