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]
]
分析
利用上一題的思路试溯，一直遍歷記錄路徑和虱岂，直到達(dá)到葉子節(jié)點(diǎn)，并且和為指定值。本題需要輸出路徑夜只，需要多加一個(gè)臨時(shí)數(shù)組來(lái)保存路徑，當(dāng)滿(mǎn)足情況時(shí)，記錄在二維數(shù)組中即可。
/**
* 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;
}
