[257] Binary Tree Paths

看起來是一個在 C＋＋很easy的題目，放到C 卻充滿陷阱的題目 >< !

寫了一個版本終於可以對應出inneridx 跟out idx ，還想說雖然先宣告了maximum的ret array size 最後還要處理一下，但似！！！！！！

原來我回傳的時候會把上一層或上上層總之它以上的會沒辦法紀錄到QQ

看到別人的解決辦法是，另用一個string cur 去存目前從root 帶下來的字串是什麼，

或者有一個作法是用int array 先把前面經過過的 node value 存起來

到了leaf 要回傳的時候再一次轉換成字串。

先把自己的 "不正確版" 貼一下，反正recursive 的部分是對的吧XD

剩下的是處理沿途紀錄的部分 QQ

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

* };

*/

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

int running(struct TreeNode* root, int inner_idx, int out_idx, char** ret )

{

if (root==NULL)

return out_idx;

if (root->left == NULL && root-> right == NULL)

{

char *buff = calloc (8, sizeof(char));

sprintf(buff, "%d", root->val);

int inLen= strlen(buff);

strncpy(&(ret[out_idx][inner_idx]), buff, inLen);

return ++out_idx;

}

char *buff = calloc (8, sizeof(char));

sprintf(buff, "%d->", root->val);

int inLen= strlen(buff);

strncpy(&(ret[out_idx][inner_idx]), buff, inLen);

if (root->left != NULL && root->right != NULL)

strncpy(&(ret[out_idx+1][inner_idx]), buff, inLen);

inner_idx += inLen;

out_idx = running(root->left, inner_idx, out_idx, ret);

out_idx = running(root->right, inner_idx, out_idx, ret);

return out_idx;

}

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

int idx = 0, leafcount = 0;

int maxLen=600;

int maxLeaf = 128; //less than

char **ret = calloc (maxLeaf, sizeof(char*));

for (int i=0;i< maxLeaf; i++)

ret[i]= calloc (maxLen, sizeof(char));

leafcount = running(root, idx, leafcount, ret);

*returnSize = leafcount;

return ret;

}

哦最後我竟然可以大概寫出來而不要看太多解法 XD

用一個current string 去存的話，要住意append （strcat）不能用在傳進來的那個字串上，

因為它recursive 兩層以後，再回來的時候已經 （被）長大了！！！

int running(struct TreeNode* root, int out_idx, char** ret, char *cur )

{

if (root==NULL)

return out_idx;

if (root->left == NULL && root-> right == NULL)

{

sprintf(&(ret[out_idx][0]),"%s%d", cur, root->val);

return ++out_idx;

}

char *buff = calloc (128, sizeof(char));

sprintf(buff,"%s%d->", cur, root->val);

out_idx = running(root->left, out_idx, ret, buff);

out_idx = running(root->right, out_idx, ret, buff);

return out_idx;

}

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

int leafcount = 0;

int maxLen= 100;

int maxLeaf = 50; //less than

char *cur = calloc (maxLen, sizeof (char));

char **ret = calloc (maxLeaf, sizeof(char*));

for (int i=0;i< maxLeaf; i++)

ret[i]= calloc (maxLen, sizeof(char));

leafcount = running(root, leafcount, ret, cur);

*returnSize = leafcount;

return ret;

}