Des:

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
首先看题目描述：给出一个顺序的单向链表，把它转换成一个平衡二叉树（开始还以为heiight在指高度，后来发现并不是这样）。

Question:

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {TreeNode}
 */

var sortedListToBST = function(head) {
};

Mind:

既然是一个链表转换成平衡二叉树，也就是说我们设计一个算法，该算法会得出一个根节点/左子树/右子树即可，然后对左右子树不断递归该算法即可。

Answer:

//head 则为你的链表
var sortedListToBST = function(head) {
    if(!head) return null;   //链表为空则返回null   
    if(!head.next) return new TreeNode(head.val);  //head的下一个为空 则说明只有一个值，直接生成一个树

    var mid=head; 
    var pre=head;
    var last=head;
    
   //下面的while循环是为了确认根和子树，last移动2次，mid移动一次，pre为上次的mid，这种移动保证了mid两边的相对平衡
    while(last){
        last=last.next;
        if(last){
            pre=mid;
            mid=mid.next;
            last=last.next;
        }
    }
    
    pre.next=null;  // 注意pre 是做的对象引用 这里操作pre.next值为null，其实改变的是head中对应的next的值
    var root=new TreeNode(mid.val);  //递归调用
    root.left=sortedListToBST(head); //递归调用
    root.right=sortedListToBST(mid.next);//递归调用
    return root; 
};

Source URL:

<a href="https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/#/description">leetcode传送门</a>
<a href="https://github.com/yuanhaoyu/leetcode-review/blob/master/2017/109.js">codeDemo传送门</a>