# LeetCode: 257. 二叉树的所有路径¶

## 1、题目描述¶

输入:

1
/   \
2     3
\
5



## 2、解题思路¶

​ 递归查找

​ 如果有子节点，就继续向下找

​ 如果是叶子节点，构造字符串，返回

​ 不是叶子节点，将左右子节点的所有的字符串重新构造，向上返回

/**
* 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().
*/

const char *direction = "->";

char *numToString(int n) {
int length = 1;
int temp = n;
while (temp > 0) {
temp /= 10;
length++;
}

char *result = (char *) malloc(sizeof(char) * (length + 1));
sprintf(result, "%d", n);

return result;
}

void freeBuff(char **buf, int size) {
for (int i = 0; i < size; i++) {
free(buf[i]);
}
}

char **binaryTreePath(struct TreeNode *root, int level, int *returnSize) {

char **result;
// 没有左右节点

// 当前节点的值
char *num = numToString(root->val);

// 如果是根节点
if (root->left == NULL && root->right == NULL) {
result = (char **) malloc(sizeof(char *));
if (level == 0) {
*result = num;
} else {
*result = (char *) malloc(sizeof(char) * (strlen(num) + 3));
(*result)[0] = '\0';
strcat(*result, direction);
strcat(*result, num);
free(num);
}

*returnSize = 1;
return result;

}

// 有左右节点，不是根节点
char **left;
char **right;
int left_size = 0;
int right_size = 0;

if (root->left) {
left = binaryTreePath(root->left, level + 1, returnSize);
left_size = *returnSize;
}

if (root->right) {
right = binaryTreePath(root->right, level + 1, returnSize);
right_size = *returnSize;
}

*returnSize = left_size + right_size;

result = (char **) malloc(sizeof(char *) * (left_size + right_size));

if (level == 0) {

for (int i = 0; i < left_size; i++) {
result[i] = (char *) malloc(sizeof(char) * (strlen(left[i]) + strlen(num) + 1));
result[i][0] = 0;
strcat(result[i], num);
strcat(result[i], left[i]);

}
for (int i = 0; i < right_size; i++) {
result[i + left_size] = (char *) malloc(sizeof(char) * (strlen(right[i]) + strlen(num) + 1));
result[i + left_size][0] = 0;
strcat(result[i + left_size], num);
strcat(result[i + left_size], right[i]);
}

} else {
for (int i = 0; i < left_size; i++) {
result[i] = (char *) malloc(sizeof(char) * (strlen(left[i]) + strlen(num) + 3));
result[i][0] = 0;
strcat(result[i], direction);
strcat(result[i], num);
strcat(result[i], left[i]);
}
for (int i = 0; i < right_size; i++) {
result[i + left_size] = (char *) malloc(sizeof(char) * (strlen(right[i]) + strlen(num) + 3));
result[i + left_size][0] = 0;
strcat(result[i + left_size], direction);
strcat(result[i + left_size], num);
strcat(result[i + left_size], right[i]);

}
}

free(num);
freeBuff(left, left_size);
freeBuff(right, right_size);
return result;

}

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

if (!root) {
*returnSize = 0;
return NULL;
}

return binaryTreePath(root, 0, returnSize);

}