LEET code -- Binary Tree Paths

 Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

我寫的有一個BUG 最後一個數字 如果小<10 pre="">
但是我自己程式裡面沒有  會傳回去給外面才會出現  莫名...

因為我寫的是一定要看他長度多少 才會給多少
事實上豪邁一點 一口氣給大一點也沒差

最奇怪的是 我在45 55那邊有free  但是會掛
不知為啥

還有字串複製 用strcpy最保險了




 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * 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().
 */
char** binaryTreePaths(struct TreeNode* root, int* returnSize) {
    if(!root)return NULL;
    int lesize=0,risize=0;
    char **le,**ri;
    char apd[100]={};
    sprintf(apd,"%d->\0",root->val);
    int apdSize=strlen(apd);
    le=binaryTreePaths(root->left,&lesize);
    ri=binaryTreePaths(root->right,&risize);
    
    if(le==NULL && ri==NULL){
        char **ans=calloc(1,sizeof(char*));
        
        //char te=root->val+'0'; //fail 
        char te[10]={};
        sprintf(te,"%d\0",root->val);
        ans[0]=calloc(strlen(te)+1,sizeof(char));
        //printf("s\n");
        strcpy(ans[0],te);
        printf("%s\n",ans[0]);
        *returnSize=1;
        return ans;
    }
    
    char **ans=calloc(lesize+risize,sizeof(char*));
   // printf("%d %d\n",lesize,risize);
    for(int i=0;i<lesize;i++){
        int size=strlen(le[i]);
        ans[i]=calloc(size+apdSize,sizeof(char));
        strcpy(ans[i],apd);
        strcat(ans[i],le[i]);
        ans[i][size+apdSize]='\0';
        //free(le[i]);
        printf("le %s^\n",ans[i]);
    }
    for(int i=0;i<risize;i++){
        int size=strlen(ri[i]);
        ans[lesize+i]=calloc(size+apdSize,sizeof(char));
        strcpy(ans[lesize+i],apd);
        strcat(ans[lesize+i],ri[i]);
        ans[lesize+i][size+apdSize]='\0';
        //free(ri[i]);
        printf("ri %s^\n",ans[lesize+i]);
    }
    //if(le!=NULL && lesize>1)free(le);//if lesize==1, then in the for loop will free the 0
    //if(ri!=NULL && risize>1)free(ri);
    *returnSize=lesize+risize;
    //printf("%s \n",ans[-1]);
    return ans;
}





--------

別人的寫法   也是很厲害的



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
void dfs(char **ra, struct TreeNode* root, int* returnSize, char* path, int lp){

int i,r;
char temp[10];

//lp = last position
path[lp] = root->val;
lp++;

if(root->left == NULL && root->right == NULL)
{
    (*returnSize)++;
    r = (*returnSize)-1;

    ra[r] = malloc(sizeof(char) *10 *lp);
    ra[r][0] = '\0';

    for(i = 0; i< lp-1;i++){
        sprintf(ra[r],"%s%d->",ra[r], path[i]);
    }
    sprintf(ra[r],"%s%d",ra[r], path[i]);

    return;
}

if(root->left != NULL){
    dfs(ra,root->left,returnSize,path,lp);
}    
if(root->right != NULL){
    dfs(ra,root->right,returnSize,path,lp);
}
return;

}

char** binaryTreePaths(struct TreeNode* root, int* returnSize) {

char** ra; //returnArray
int* path;

int size = 200;

if(root == NULL)
    return NULL;

path = malloc(sizeof(int ) * size);
ra = malloc(sizeof(char *) * size);

(*returnSize) = 0;
dfs(ra,root,returnSize,path,0);

return ra; 

}