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>
