正文

109.convertsortedlisttobinarysearchtree(代码片段)

hankunyan  hankunyan  2022-12-25  520

关键词：

和 148. Sort List 一样的思路，需要把链表一分为二，利用快慢指针即可。

需要注意的是，写完一定要两个节点三个节点代入几个 test case 检查一下，非常容易出错。下面做法是把最后slow的位置作为 root，递归左半边和右半边。

时间复杂度 O(nlogn) 空间复杂度 O(h)

class Solution 
public:
    TreeNode* sortedListToBST(ListNode* head) 
        return buildBST(head);
    
    
    TreeNode *buildBST(ListNode *head) // mid as root
        if (head==NULL) return NULL;
        if (head->next==NULL) return new TreeNode(head->val);
        
        ListNode *slow=head, *fast=head, *prev;
        while (fast!=NULL && fast->next!=NULL)
            fast = fast->next->next;
            prev = slow;
            slow = slow->next;
        
        prev->next = NULL;
        ListNode *mid=slow;
        TreeNode *root=new TreeNode(mid->val);
        root->left  = buildBST(head); 
        root->right = buildBST(mid->next);
        return root;
    
;