C code for bin tree paths. Can I make it simpler?


  • 1
    R
    #define MAX_SIZE 1000
    
    void pre_order_str(struct TreeNode *root, char ***res, int *res_size, char str[]) {
      
      if(NULL == root)
        return;
    
      char buf[MAX_SIZE];
      int append_size = 0;
      snprintf(buf, MAX_SIZE, "%d", root->val);
      append_size = strlen(buf);
      if(strnlen(str, MAX_SIZE) >= 1) {
        strncat(str, "->", MAX_SIZE);
        append_size += 2;
      }
      strncat(str, buf,MAX_SIZE);
      
      pre_order_str(root->left, res, res_size, str);
      pre_order_str(root->right, res, res_size, str);
      
      /*If leaf */
      if((!root->left) && (!root->right)) {    
        (*res_size)++;
        (*res) = realloc((*res), sizeof(char *) * (*res_size));
        int size = (*res_size) - 1;
    
        (*res)[size] = malloc(sizeof(char) * MAX_SIZE);
        strncpy((*res)[size], str, MAX_SIZE);
      }  
      
      /* when done with node remove ->val from str */
      str[strnlen(str, MAX_SIZE) - append_size] = '\0';  
    }
    
    char** binaryTreePaths(struct TreeNode* root, int* returnSize) {
      
      char **result = malloc(sizeof(char *) * 1);
      if(NULL == result) {
        *returnSize = 0;
        return NULL;
      }
      
      char str[MAX_SIZE];
      str[0] = '\0';
      
      pre_order_str(root, &result, returnSize, str);
      
      return result;
      
    }

  • 1

    After some modifications, I think the following code can be more readable and easy-understanding which also is accepted with 4ms.

    Can someone else to paste the 0ms-solution? Thanks for sharing!


    #define LEN 1000
    struct TreeNode
    {
        int val;
        struct TreeNod *left, *right;
    };
    void traverse( struct TreeNode* root, struct TreeNode** stack, int top, char** sArr, int* count )
    {
        if(!root->left && !root->right) //reaching the leaf node, let's collect now;
        {
            sArr[*count] = (char*)malloc(sizeof(char)*LEN);
            sArr[*count][0] = '\0';
            int i = 0;
            char* s = (char*)malloc(sizeof(char)*30);
            for(; i < top; i++)
            {
                snprintf(s, 30, "%d", stack[i]->val);
                strcat(sArr[*count], s);
                strcat(sArr[*count], "->");
            }
            snprintf(s, 30, "%d", stack[i]->val);
            strcat(sArr[*count], s);
            (*count)++;
        }
        else //not the leaf, inner node;
        {
            if(root->left)
            {
                stack[top+1] = root->left;
                traverse(root->left, stack, top+1, sArr, count);
            }
            if(root->right)
            {
                stack[top+1] = root->right;
                traverse(root->right, stack, top+1, sArr, count);
            }
        }
    }
    
    //AC - 4ms;
    char** binaryTreePaths( struct TreeNode* root, int* returnSize )
    {
        if(root == NULL) return NULL;
        int top = -1;
        struct TreeNode **stack = ( struct TreeNode **)malloc(sizeof( struct TreeNode *)*LEN);
        stack[++top] = root;
        char** ss = (char**)malloc(sizeof(char*)*LEN);
        traverse(root, stack, top, ss, returnSize);
        return ss;
    }

  • 0
    F

    I try four times, two is 0ms, the other is 4ms.
    Same logic.

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
    /**
     * Return an array of size *returnSize.
     * Note: The returned array must be malloced, assume caller calls free().
     */
    void save(char ***res, int *size, int *returnSize, char **line, int llen) {
        if (*returnSize == *size) {
            *size += 1000;
            *res = realloc(*res, *size * sizeof(char *));
        }
        char *tmp = malloc(llen + 1);
        memcpy(tmp, *line, llen);
        tmp[llen] = 0;
        (*res)[(*returnSize)++] = tmp;
    }
    void helper(struct TreeNode *root, char ***res, int *size, int *returnSize, char **line, int *lsize, int llen) {
        if (llen + 30 >= *lsize) {
            *lsize += 1000;
            *line = realloc(*line, *lsize);
        }
        if (llen != 0) {
            (*line)[llen++] = '-';
            (*line)[llen++] = '>';
        }
        char tmp[30] = {0};
        sprintf(tmp, "%d", root->val);
        char *p;
        for (p = tmp; *p; p++) {
            (*line)[llen++] = *p;
        }
        if (!root->left && !root->right) {
            save(res, size, returnSize, line, llen);
            return;
        }
        if (root->left) helper(root->left, res, size, returnSize, line, lsize, llen);
        if (root->right) helper(root->right, res, size, returnSize, line, lsize, llen);
    }
    char** binaryTreePaths(struct TreeNode* root, int* returnSize) {
        if (!root) return 0;
        int size = 1000;
        char **res = malloc(size * sizeof(char *));
        *returnSize = 0;
        int lsize = 1000;
        int llen =  0;
        char *line = malloc(lsize);
        helper(root, &res, &size, returnSize, &line, &lsize, llen);
        return res;
    }

  • 0
    J

    @LHearen said in C code for bin tree paths. Can I make it simpler?:

    snprintf

    what is "30" here? A magic number??


Log in to reply
 

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