2014
09-10

# 有序链表转化为平衡的二分查找树

### Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Java代码如下：

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; next = null; }
* }
*/
/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
}
//用快慢指针找到中间节点
ListNode preSlow = null;
while(fast.next != null && fast.next.next != null){
preSlow = slow;
slow = slow.next;
fast = fast.next.next;
}
//分别递归左右两部分
TreeNode mid = new TreeNode(slow.val);
if(preSlow != null){
preSlow.next = null;
}
if(slow.next != null){
mid.right = sortedListToBST(slow.next);
}
return mid;
}
}

方法二

BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {
if (start > end) return NULL;
// same as (start+end)/2, avoids overflow
int mid = start + (end - start) / 2;
BinaryTree *leftChild = sortedListToBST(list, start, mid-1);
BinaryTree *parent = new BinaryTree(list->data);
parent->left = leftChild;
list = list->next;
parent->right = sortedListToBST(list, mid+1, end);
return parent;
}

BinaryTree* sortedListToBST(ListNode *head, int n) {
}

//============================================================================
// Name        : SortedListToBST.java
// Author      : GaoTong
// Date        : 2014/9/7
//============================================================================
public class SortedListToBST {

public static TreeNode sortedListToBST(ListNode head) {
int len = 0;
while(tmp != null){
len++;
tmp = tmp.next;
}
}

public static TreeNode sortedListToBST(ListNodeWrapper headWrapper, int start, int end){
if(start > end) return null;
int mid = start + (end-start)/2;
TreeNode left = sortedListToBST(headWrapper, start, mid-1);
parent.left = left;
}