C solution (0ms) - Iterative and recursive


  • 0

    Iterative solution: uses a realloc/memcpy based queue (the memcpy on every dequeue is expensive, however, it is a fast alternative to writing a linked list based queue, for the purpose of solving programming problems in C)

    #define queue_new(q)        int *q = NULL; int q##Size = 0
    #define queue_size(q)       q##Size
    #define queue_empty(q)      (q##Size == 0)
    #define queue_peek(q)       q[0]
    #define queue_enqueue(q, n) q = realloc(q, ++q##Size * sizeof(int)); q[q##Size - 1] = n
    #define queue_dequeue(q)    memcpy(q, q + 1, --q##Size * sizeof(int)); \
                                q = realloc(q, q##Size * sizeof(int))
    
    int* rightSideView(struct TreeNode* root, int* returnSize) {
        if (!root) return NULL;
        int *result = NULL;
        queue_new(nodeQ);
        queue_enqueue(nodeQ, root);
        int levelSize = queue_size(nodeQ);
        while (!queue_empty(nodeQ)) {
            struct TreeNode *node = queue_peek(nodeQ);
            queue_dequeue(nodeQ);
            levelSize--;
            if (node->left) { queue_enqueue(nodeQ, node->left); }
            if (node->right) { queue_enqueue(nodeQ, node->right); }
            if (levelSize == 0) {
                levelSize = queue_size(nodeQ);
                result = realloc(result, ++(*returnSize) * sizeof(int));
                result[*returnSize - 1] = node->val;
            }
        }
        return result;
    }
    

    Recursive solution:

    void rightSideViewHelper(struct TreeNode *node, int **result, int *resultSize, int depth) {
        if (node == NULL) { return; }
        if (*resultSize == depth) {
            *result = realloc(*result, ++(*resultSize) * sizeof(int));
            (*result)[*resultSize - 1] = node->val;
        }
        rightSideViewHelper(node->right, result, resultSize, depth + 1);
        rightSideViewHelper(node->left, result, resultSize, depth + 1);
    }
    
    int* rightSideView(struct TreeNode* root, int* returnSize) {
        int *result = NULL;
        *returnSize = 0;
        rightSideViewHelper(root, &result, returnSize, 0);
        return result;
    }
    

Log in to reply
 

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