# [LeetCode] 109. Convert Sorted List to Binary Search Tree 把有序链表转成二叉搜索树

2021年09月15日 阅读数：1

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

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.java

Example:node

```Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

0
/ \
-3   9
/   /
-10  5```

108. Convert Sorted Array to Binary Search Tree  思路同样，只不过一个是数组，一个是链表。数组能够经过index直接访问元素找到中点，而链表的查找中间点要经过快慢指针来操做。python

Java:数组

```class Solution {
}
public TreeNode toBST(ListNode head, ListNode tail){

while(fast!=tail&&fast.next!=tail){
fast = fast.next.next;
slow = slow.next;
}
}
} 　　```

Python:post

```class ListNode:
def __init__(self, x):
self.val = x
self.next = None

class Solution:
# @param head, a list node
# @return a tree node
while current is not None:
current, length = current.next, length + 1
return self.sortedListToBSTRecu(0, length)

def sortedListToBSTRecu(self, start, end):
if start == end:
return None
mid = start + (end - start) / 2
left = self.sortedListToBSTRecu(start, mid)
current.left = left
current.right = self.sortedListToBSTRecu(mid + 1, end)
return current
```

Python:ui

```def sortedListToBST(self, head):
return

while fast and fast.next:
fast = fast.next.next
slow = slow.next

tmp = slow.next
slow.next = None
root = TreeNode(tmp.val)
root.right = self.sortedListToBST(tmp.next)

return root　　```

C++:this

```class Solution {
public:
int n = 0;
while (curr) {
curr = curr->next;
++n;
}
}

TreeNode * BuildBSTFromSortedDoublyListHelper(ListNode **head, int s, int e) {
if (s == e) {
return nullptr;
}

int m = s + ((e - s) / 2);
auto left = BuildBSTFromSortedDoublyListHelper(head, s, m);

curr->left = left;
curr->right = BuildBSTFromSortedDoublyListHelper(head, m + 1, e);
return curr;
}
};
```