Des:
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
首先看題目描述：給出一個順序的單向鏈表妖混，把它轉(zhuǎn)換成一個平衡二叉樹（開始還以為heiight在指高度蓄愁，后來發(fā)現(xiàn)并不是這樣）。
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:
既然是一個鏈表轉(zhuǎn)換成平衡二叉樹，也就是說我們設(shè)計一個算法，該算法會得出一個根節(jié)點/左子樹/右子樹即可，然后對左右子樹不斷遞歸該算法即可馏谨。
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循環(huán)是為了確認根和子樹附迷，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中對應(yīng)的next的值
var root=new TreeNode(mid.val); //遞歸調(diào)用
root.left=sortedListToBST(head); //遞歸調(diào)用
root.right=sortedListToBST(mid.next);//遞歸調(diào)用
return root;
};
Source URL:
<a >leetcode傳送門</a>
<a >codeDemo傳送門</a>
