C 代码
/**
* 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().
*/
#include <stdio.h>
#define N 100010
void DFS(struct TreeNode* p,int sum,int total,int** columnSizes,int *returnSize,int* path,int idx,int** res)
{
if (!p->left && !p->right && sum == total) {
//这里开辟了数组的第二维
res[*returnSize] = (int*)malloc(N * sizeof(int));
for (int i=0;i<=idx;i++) res[*returnSize][i] = path[i];
//告知主函数这一行的列数
(*columnSizes)[*returnSize] = idx + 1;
//通过整数的指针来改变主函数中整数的值,告知主函数现在行数+1了
(*returnSize)++;
return;
}
if (p->left) {
path[idx+1] = p->left->val;
DFS(p->left,sum,total+p->left->val,columnSizes,returnSize,path,idx+1,res);
}
if (p->right) {
path[idx+1] = p->right->val;
DFS(p->right,sum,total+p->right->val,columnSizes,returnSize,path,idx+1,res);
}
}
//此题难点在于传参
//returnSize是一个指向整数的指针,*returnSize指返回的数组的行数
//将这个数给到主函数让它知道应该检查多少行数据,告知它多余的数据是我们开出来防止溢出的
//为什么不直接传入一个整数来让我们设定行数呢?因为改变传入的整数参数并不能改变它在主函数内的值
//主函数中的调用可能如下:
//for (int i=0;i<*returnSize;i++) col[i]...... (可以看出col是一维数组的指针)
//若col[0] = 5,表示第一行结果有5列,主函数会去检查我们返回的数组第一行的前5列,不再管后面的
//传入给我们的columnSizes实际上是&col
//所以columnSizes是一个一维数组的指针的指针,*columnSizes是一个一维数组
//*columnSizes(col)中存储的是每一行有多少列,因为每条路径的长度是不一样的,主函数需要知道每行需要检测多少列(多长)
//为什么主函数不直接传入col这个指针而要传入col的地址呢?
//与上文同理,如果直接将一个数组的指针赋值给col这一指针变量,主函数中的col的值是无法被改变的
//为了直接给*columnSizes赋一个数组的指针,主函数传入了** columnSizes
int** findPath(struct TreeNode* root, int sum, int** columnSizes, int* returnSize) {
//首先将要检查的行数初始化为0
*returnSize = 0;
//空树没有可走的路径,返回NULL
if (!root) return NULL;
//创建一个数组来存储返回的数据,但它的大小不决定主函数的判断范围,主函数会依据columnSizes和returnSise判断
//这里只开辟了数组的一维
int** res = (int**)malloc(N * sizeof(int*));
//存储路径
int path[N],idx = 0;
path[0] = root->val;
//当前已经加到的和
int total = root->val;
DFS(root,sum,total,columnSizes,returnSize,path,idx,res);
return res;
}