链表转换二叉搜索树(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;}
};
更多推荐
[二叉树]leetcode109:有序链表转换二叉搜索树(medium)
发布评论