安徽通皖建设工程有限公司网站百度app下载官方免费下载安装

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：[]

示例 3：

输入：root = [1,2], targetSum = 0
输出：[]

代码：

/*** 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 *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/#define Maxsize 1024// returnSize: 一个指针，用于返回满足条件的路径数量（即最终返回的二维数组的行数）
// returnColumnSizes: 一个指针，用于返回一个数组，该数组存储最终返回的二维数组中每条路径的长度（即二维数组中每列的长度）
// result: 二维整数数组指针，用于存储满足条件的路径数组
// temp: 整数数组，用于临时存储从根节点到当前节点遍历过程中的路径上的节点值
// NodeNum: 用于暂存当前路径上的节点数量
void DFS(struct TreeNode* root, int sum, int* returnSize, int** returnColumnSizes, int** result, int* temp, int NodeNum)
{// 如果当前节点的值等于目标和sum，并且当前节点是叶子节点（即没有左子节点且没有右子节点）if (root->val == sum && root->left == NULL && root->right == NULL){// 将当前节点的值添加到临时路径数组temp中，并更新当前路径上的节点数量NodeNumtemp[NodeNum++] = root->val;// 为当前满足条件的路径分配内存空间，大小为当前路径上的节点数量乘以每个节点值占用的空间result[*returnSize] = malloc(NodeNum * sizeof(int));// 将临时路径数组temp中的值复制到刚分配好的内存空间中，形成一条完整的满足条件的路径for (int i = 0; i < NodeNum; i++){result[*returnSize][i] = temp[i];}// 将当前路径的长度（即NodeNum）存储到用于记录每条路径长度的数组returnColumnSizes中，并更新满足条件的路径数量*returnSize(*returnColumnSizes)[(*returnSize)++]= NodeNum;}else{// 将当前节点的值添加到临时路径数组temp中，并更新当前路径上的节点数量NodeNumtemp[NodeNum++]= root->val;// 如果当前节点的左子节点不为空，递归调用DFS函数继续在左子树中寻找满足条件的路径// 此时目标和更新为sum减去当前节点的值，因为已经将当前节点的值加入到了路径中if (root->left!= NULL) DFS(root->left, sum - root->val, returnSize, returnColumnSizes, result, temp, NodeNum);// 如果当前节点的右子节点不为空，递归调用DFS函数继续在右子树中寻找满足条件的路径// 同样，目标和更新为sum减去当前节点的值if (root->right!= NULL) DFS(root->right, sum - root->val, returnSize, returnColumnSizes, result, temp, NodeNum);}
}// returnSize: 一个指针，用于返回满足条件的路径数量（即最终返回的二维数组的行数）
// returnColumnSizes: 一个指针，用于返回一个数组，该数组存储最终返回的二维数组中每条路径的长度（即二维数组中每列的长度）
int** pathSum(struct TreeNode* root, int sum, int* returnSize, int** returnColumnSizes)
{// 如果根节点为空，说明是空树，直接返回NULL，表示没有找到满足条件的路径if (root == NULL) return NULL;// 定义一个整数数组temp，用于临时存储从根节点到当前节点遍历过程中的路径上的节点值，假设最多能容纳Maxsize个节点值int temp[Maxsize];// 初始化返回的二维整数数组，用于存储满足条件的路径数组，假设最多能容纳Maxsize条路径int** result = malloc(Maxsize * sizeof(int*));// 为用于记录每条路径长度的数组分配内存空间，假设最多能容纳Maxsize条路径的长度信息*returnColumnSizes = malloc(Maxsize * sizeof(int));// 初始化满足条件的路径数量为0*returnSize = 0;// 调用DFS函数开始在二叉树中深度优先搜索，寻找满足条件的路径DFS(root, sum, returnSize, returnColumnSizes, result, temp, 0);// 返回存储满足条件的路径的二维数组，调用者可以通过该数组获取所有满足条件的路径及其长度信息return result;
}