首页 > 其他 > 详细

Convert Sorted List to Binary Search Tree

时间:2017-06-08 16:15:32      阅读:244      评论:0      收藏:0      [点我收藏+]

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

原文:http://www.cnblogs.com/agentgamer/p/6963372.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!