成都网站设计推荐,网站建设企业网站界面设计,小兽wordpress官网,合肥学做网站app的学校给你二叉树的根节点 root 和一个整数目标和 targetSum #xff0c;找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。 示例 1#xff1a; 输入#xff1a;root [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum 22
输出找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。 示例 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;
}
