Why my C O(n) code ran fine on Linux box but got an OJ run-time error given input {1}?


  • 0
    D
    struct list_node {
        struct TreeNode *node;
        struct list_node *next;
        struct list_node *prev;
    };
     
    struct list_node head;
    
    void init_queue(struct list_node *head)
    {
        if (!head)
            return;
        
        head->node = NULL;
        head->next = head;
        head->prev = head;
    }
    
    void enqueue(struct list_node *head, struct TreeNode *tn)
    {
        struct list_node *ln;
         
        if (!head)
            return;
        
        if (!tn)
            return;
    
        ln = malloc(sizeof(struct list_node));
        if (!ln)
            return;
            
        ln->node = tn;
        ln->next = ln->prev = NULL;
        
        ln->next = head->next;
        ln->prev = head;
        head->next->prev = ln;
        head->next = ln;
    }
     
    struct TreeNode *dequeue(struct list_node *head)
    {
        struct list_node *ln;
        struct TreeNode *tn;
        
        if (!head)
            return NULL;
        
        if (head->next == head)
            return NULL;
        
        ln = head->prev;
        
        ln->prev->next = head;
        head->prev = ln->prev;
        
        tn = ln->node;
        
        free(ln);
        
        return tn;
    }
    
    int queue_is_empty(struct list_node *head)
    {
        if (!head)
            return 1;
        
        return (head->next == head) ? 1 : 0;
    }
    
    int out[128];
    
    int *rightSideView(struct TreeNode *root, int *n) 
    {
        int cur_level_num = 0;
        int next_level_num = 0;
        struct TreeNode *node;
        
        if (!n)
            return 0;
    
        *n = 0;
        
        if (!root)
            return out;
        
        init_queue(&head);
        
        enqueue(&head, root);
        cur_level_num = 1;
    
        while(!queue_is_empty(&head)) {
    
            node = dequeue(&head);
            if (!node)
                break;
    
            cur_level_num--;
            
            if (node->left) {
                enqueue(&head, node->left);
                next_level_num++;
            }
    
            if (node->right) {
                enqueue(&head, node->right);
                next_level_num++;
            }
            
            if (!cur_level_num) {
                out[*n] = node->val;
                *n = (*n) + 1;
                cur_level_num = next_level_num;
                next_level_num = 0;
            }
        }
        
        return out;
    }

  • 0
    D

    Figured it out. OJ expects the return to be dynamic allocated buffer and will try to free it after checking its content, so static buffer (.bss or .data) can't be used as the return. The basic idea is BFS.

    Here is the version that got accepted.

    /**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     * 
     * Fill out 'n' to indicate how many elements return.
     */
     
     
    struct list_node {
        struct TreeNode *node;
        struct list_node *next;
        struct list_node *prev;
    };
     
    struct list_node head;
    
    void init_queue(struct list_node *head)
    {
        if (!head)
            return;
        
        head->node = NULL;
        head->next = head;
        head->prev = head;
    }
    
    void enqueue(struct list_node *head, struct TreeNode *tn)
    {
        struct list_node *ln;
         
        if (!head)
            return;
        
        if (!tn)
            return;
    
        ln = malloc(sizeof(struct list_node));
        if (!ln)
            return;
            
        ln->node = tn;
        ln->next = ln->prev = NULL;
        
        ln->next = head->next;
        ln->prev = head;
        head->next->prev = ln;
        head->next = ln;
    }
     
    struct TreeNode *dequeue(struct list_node *head)
    {
        struct list_node *ln;
        struct TreeNode *tn;
        
        if (!head)
            return NULL;
        
        if (head->next == head)
            return NULL;
        
        ln = head->prev;
        
        ln->prev->next = head;
        head->prev = ln->prev;
        
        tn = ln->node;
        
        free(ln);
        
        return tn;
    }
    
    int queue_is_empty(struct list_node *head)
    {
        if (!head)
            return 1;
        
        return (head->next == head) ? 1 : 0;
    }
    
    
    int *rightSideView(struct TreeNode *root, int *n) 
    {
        int cur_level_num = 0;
        int next_level_num = 0;
        struct TreeNode *node;
        int *out = NULL;
        
        if (!n)
            return out;
    
        *n = 0;
        
        if (!root)
            return out;
        
        out = malloc(128 * sizeof(int));
        if (!out)
            return NULL;
    
        init_queue(&head);
        
        enqueue(&head, root);
        cur_level_num = 1;
    
        while(!queue_is_empty(&head)) {
    
            node = dequeue(&head);
            if (!node)
                break;
    
            cur_level_num--;
            
            if (node->left) {
                enqueue(&head, node->left);
                next_level_num++;
            }
    
            if (node->right) {
                enqueue(&head, node->right);
                next_level_num++;
            }
            
            if (!cur_level_num) {
                out[*n] = node->val;
                *n = (*n) + 1;
                cur_level_num = next_level_num;
                next_level_num = 0;
            }
        }
        
        return out;
    }

Log in to reply
 

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