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

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

python代码：

```class Solution(object):

"""
:rtype: TreeNode
:author: 凌风技术站-iaccepted
"""

return None

# 找到中心节点的前一个节点

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

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

# 求单链表中间节点的方法
while fast != None and fast.next != None:
fast = fast.next.next
slow = slow.next
return slow
```

c++代码：

```class Solution {
//author: 凌风技术站-iaccepted
public:

//先将所有的值存入一个vector，然后方便后面快速建树
ivec.push_back(0);
{
}

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;
};
```