[二叉树]leetcode109：有序链表转换二叉搜索树(medium)

链表转换二叉搜索树(medium)"/>

[二叉树]leetcode109：有序链表转换二叉搜索树(medium)

题目：

题解：

思路：用两个指针，一块一慢，快的每次走两步，慢的每次走一步，这样当快指针遍历结束时，慢指针指向的也就是链表的中间位置。这时候把中间位置的节点的值作为二叉搜索树根节点的值。因为二叉搜索树对应的就是一个有序数组，根节点对应的元素值为为有序数组最中间的位置。

代码如下：

class Solution {
public:TreeNode* sortedListToBST(ListNode* head) {if(head==nullptr)return nullptr;if(head->next==nullptr)return new TreeNode(head->val);//设置快慢指针用来找到链表的中点，当fast指针走到尾时，slow指针指向链表中点，pre为slow中点的前一个节点ListNode *pre=head,*slow=head->next,*fast=head->next->next;while(fast!=nullptr&&fast->next!=nullptr){pre=pre->next;slow=slow->next;fast=fast->next->next;}//将中点左边的链表断开pre->next=nullptr;TreeNode* root=new TreeNode(slow->val);//二叉搜索的根节点为数组最中间的数root->left=sortedListToBST(head);//根节点的左子树连接链表的前半部分root->right=sortedListToBST(slow->next);//根节点的右子树连接链表的后半部分return root;}
};