首页 > 代码库 > Convert Sorted List to Binary Search Tree
Convert Sorted List to Binary Search Tree
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/#/description
跟数组那题没有什么本质区别，唯一的障碍是，在数组里因为长度已知，所以求中位数很方便。但是链表里找中位数就麻烦一点了。
快慢指针再一次登场了，快指针一次走两步，慢指针一次走一步。那么当快指针走到尽头的时候，慢指针就刚好指在链表的中间。
function ListNode(val) { this.val = val; this.next = null; }function TreeNode(val) { this.val = val; this.left = this.right = null;}/** * @param {ListNode} head * @return {TreeNode} */var sortedListToBST = function(head) { return ct(head, null); };function ct(head, tail) { if (!head) return null; if (head == tail) {return null;} var mid = head; var fast = head; while (fast.next !== tail && fast.next.next !== tail) { mid = mid.next; fast = fast.next.next; } var root = new TreeNode(mid.val); root.left = ct(head, mid); root.right = ct(mid.next, tail); return root;}
Convert Sorted List to Binary Search Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。