My C solution using a stack


  • 0
    K
    #define SIZE 1024
    
    char* tmp[SIZE];
    int total = 0;
    
    struct stack {
        int num[SIZE];
        int p;
    };
    
    static bool push(int n, struct stack* st) {
        if (st->p == SIZE - 1) {
            return false;
        }
        (st->p)++;
        st->num[st->p] = n;
        return true;
    }
    
    static bool pop(int *n, struct stack* st) {
        if (st->p < 0) {
            return false;
        }
        *n = st->num[st->p];
        (st->p)--;
        return true;
    }
    
    static char* stack2str(struct stack* st) {
        char build[SIZE] = {0};
        char *str = NULL;
        if (st->p < 0) {
            return NULL;
        }
        
        sprintf (build, "%d", st->num[0]);
        for (int i = 1; i <= st->p; i++) {
            sprintf (build, "%s->%d", build, st->num[i]);
        }
        str = (char *)malloc(sizeof(char) * (strlen(build) + 1));
        strcpy(str, build);
        return str;
    }
    
    void helper(struct TreeNode* root, struct stack *st) {
        if (!push(root->val, st)) {
            return;
        }
        if (!root->left && !root->right) {
            tmp[total++] = stack2str(st);
        }
        if (root->left) helper(root->left, st);
        if (root->right) helper(root->right, st);
        int unuse;
        pop(&unuse, st);
        return;
    }
    
    char** binaryTreePaths(struct TreeNode* root, int* returnSize) {
        if (!root) {
            *returnSize = 0;
            return NULL;
        }
        
        struct stack st;
        st.p = -1;
        helper(root, &st);
        
        int **ret = (int **)malloc(sizeof(int *) * total);
        *returnSize = total;
        for (int i = 0; i < total; i++) {
            ret[i] = tmp[i];
        }
        // leetcode does not clear global variable for you in different test cases so....
        total = 0;  
        
        return ret;
    }
    

Log in to reply
 

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