Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
return
[
   [5,4,11,2],
   [5,8,4,5]
]

分析

利用上一题的思路，一直遍历记录路径和，直到达到叶子节点，并且和为指定值。本题需要输出路径，需要多加一个临时数组来保存路径，当满足情况时，记录在二维数组中即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *columnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
void searchPath(struct TreeNode* root, int sum,int pathsum,int *temp,int *tempLength,int **ans, int** columnSizes, int* returnSize)
{
    if(root->left==NULL&&root->right==NULL)
    {
        if(pathsum+root->val==sum)
        {
            temp[*tempLength]=root->val;
            *tempLength=(*tempLength)+1;
            ans[*returnSize]=(int*)malloc(sizeof(int)*(*tempLength));
            for(int i=0;i<*tempLength;i++)
                ans[*returnSize][i]=temp[i];
            (*columnSizes)[*returnSize]=*tempLength;
            *returnSize=(*returnSize)+1;
            *tempLength=(*tempLength)-1;
            return ;
        }
        else return ;
    }
    if(root->left!=NULL)
    {
        temp[*tempLength]=root->val;
        *tempLength=(*tempLength)+1;
        searchPath(root->left,sum,pathsum+root->val,temp,tempLength,ans,columnSizes,returnSize);
        *tempLength=(*tempLength)-1;
    }
    if(root->right!=NULL)
    {
        temp[*tempLength]=root->val;
        *tempLength=(*tempLength)+1;
        searchPath(root->right,sum,pathsum+root->val,temp,tempLength,ans,columnSizes,returnSize);
        *tempLength=(*tempLength)-1;
    }
    return;
}
int** pathSum(struct TreeNode* root, int sum, int** columnSizes, int* returnSize) {
    int **ans=(int **)malloc(sizeof(int*)*100000);
    *columnSizes=(int*)malloc(sizeof(int)*1000);
    *returnSize=0;
    if(root==NULL)return ans;
    int *temp=(int *)malloc(sizeof(int)*1000);
    int tempLength=0;
    searchPath(root,sum,0,temp,&tempLength,ans,columnSizes,returnSize);
    return ans;
}