# [leetcode题解]109.Convert sorted list to binary search tree

leetcode 109,convert sorted list to binary search tree,给定一个已排好序的单链表，将其转换为一棵平衡二叉查找树，平衡二叉查找树要求左右子树的高度差小于等于1，而且左子树上的节点都小于等于当前根节点，有子树上的节点都大于当前根节点。

python代码：

```class Solution(object):

def sortedListToBST(self, head):
"""
:type head: ListNode
:rtype: TreeNode
:author: 凌风技术站-iaccepted
"""
return self.buildTree(head)

def buildTree(self, head):
if head is None:
return None
if head.next is None:
return TreeNode(head.val)

# 找到中心节点的前一个节点
m = self.halfNode(head)

t = m.next
m.next = None
m = t

# 先生成根节点，然后递归的去建立左子树和右子树
root = TreeNode(m.val)
root.left = self.buildTree(head)
root.right = self.buildTree(m.next)
return root

# 求单链表中间节点的方法
def halfNode(self, head):
if head is None or head.next is None:
return head
slow = head
fast = head.next.next
while fast != None and fast.next != None:
fast = fast.next.next
slow = slow.next
return slow
```

c++代码：

```class Solution {
//author: 凌风技术站-iaccepted
public:
TreeNode* sortedListToBST(ListNode* head) {
if (head == NULL)return NULL;

//先将所有的值存入一个vector，然后方便后面快速建树
ivec.push_back(0);
while(head != NULL)
{
ivec.push_back(head->val);
head = head->next;
}

int n = ivec.size() - 1;
TreeNode *root = buildTree(1, n);
return root;
}

private:
//递归的建立整棵树
TreeNode *buildTree(int l, int r)
{
if (l > r)return NULL;
int mid = (l + r) >> 1;
TreeNode *root = new TreeNode(ivec[mid]);
root->left = buildTree(l, mid - 1);
root->right = buildTree(mid + 1, r);
return root;
}
vector<int> ivec;
};
```