【二叉树】二叉树的所有路径

解题思路：回溯解决

回溯结束条件：传入结点为叶子结点

1. 先将传入的结点值放入栈中，作为路径基础
2. 如果结点非叶子结点，递归进入左右子树
   1. 切记最后将栈顶元素出栈，因为左右孩子已经用完
3. 若结点为叶子结点：
   1. 则将栈中所有元素生成字符串，用sprintf连接
      1. 这里有一个很棒的应用：sprintf（）函数返回每次写入的字符串数量，因此可以用这个返回值+字符串起始位置来得到每次需要添加的位置
   2. 最后将生成好的数组放入二维数组中

void traversal(int* returnSize, struct TreeNode* node, char** ret, int* stack, int* top) {
    stack[(*top)++] = node->val;
    if(!node->left && !node->right) {
        char* string = (char*)malloc(1000 * sizeof(char));
        int i;
        int len = 0;
        for(i = 0; i < *top - 1; i++) {
            //sprintf函数返回被写入的字符总数，这样可以一直确定要插入的数字的位置
            len += sprintf(string + len, "%d->", stack[i]);
        }
        sprintf(string + len, "%d", stack[*top-1]);
        ret[(*returnSize)++] = string;
    }
    else {
        if(node->left) {
            traversal(returnSize, node->left, ret, stack, top);
            --*top;
        }
        if(node->right) {
            traversal(returnSize, node->right, ret, stack, top);
            --*top;
        }
    }
}

char ** binaryTreePaths(struct TreeNode* root, int* returnSize){
    char** ret = (char**)malloc(1001 * sizeof(char*));
    *returnSize = 0;
    int stack[1024];
    int top = 0;
    traversal(returnSize, root, ret, stack, &top);
    return ret;
}