Clean recursive C solutuion - 8ms


  • 1
    H
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
    struct TreeNode* sortedListToBST(struct ListNode* head) {
        struct ListNode* slow = head;
        struct ListNode* fast = head;
        
        if(head == NULL) {
            return NULL;
        }
        else if(head->next == NULL){
            struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
            
            if(node == NULL) {
                return NULL;
            }
            
            node->val = head->val;
            node->left = NULL;
            node->right = NULL;
            
            return node;
        }
        
        //find the middle node
        struct ListNode* prev = NULL;
        do {
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }while(fast != NULL && fast->next != NULL);
        
        //slow is the middle node and the root node of BST
        prev->next = NULL;
        struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
            
        if(root == NULL) {
            return NULL;
        }
            
        root->val = slow->val;
        root->left = NULL;
        root->right = NULL;
        
        
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(slow->next);
        
        return root;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.