2014
11-18

# LeetCode-Convert Sorted List to Binary Search Tree[二叉树]

### 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.

// LeetCode, Convert Sorted List to Binary Search Tree
// 分治法，类似于 Convert Sorted Array to Binary Search Tree，
// 自顶向下，时间复杂度O(n^2)，空间复杂度O(logn)
class Solution {
public:
}

TreeNode* sortedListToBST (ListNode* head, int len) {
if (len == 0) return nullptr;
if (len == 1) return new TreeNode (head->val);

TreeNode* root = new TreeNode (nth_node (head, len / 2 + 1)->val);
root->left = sortedListToBST (head, len / 2);
root->right = sortedListToBST (nth_node (head, len / 2 + 2),
(len - 1) / 2);

return root;
}

int listLength (ListNode* node) {
int n = 0;

while(node) {
++n;
node = node->next;
}

return n;
}

ListNode* nth_node (ListNode* node, int n) {
while (--n)
node = node->next;

return node;
}
};


// LeetCode, Convert Sorted List to Binary Search Tree
// bottom-up，时间复杂度O(n)，空间复杂度O(logn)
class Solution {
public:
int len = 0;
while (p) {
len++;
p = p->next;
}
return sortedListToBST(head, 0, len - 1);
}
private:
TreeNode* sortedListToBST(ListNode*& list, int start, int end) {
if (start > end) return nullptr;

int mid = start + (end - start) / 2;
TreeNode *leftChild = sortedListToBST(list, start, mid - 1);
TreeNode *parent = new TreeNode(list->val);
parent->left = leftChild;
list = list->next;
parent->right = sortedListToBST(list, mid + 1, end);
return parent;
}
};


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 {
public static TreeNode sortedListToBST(ListNode head) {
int len = 0;
while(tmp != null){
len++;
tmp = tmp.next;
}
}

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