网页制作与网站建设期末考试,购物网站每个模块主要功能,山东省住房和城乡建设厅网站电话,网站开发销售简历范文给你一个二叉树的根节点 root #xff0c;按 任意顺序 #xff0c;返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。 示例 1#xff1a;
输入#xff1a;root [1,2,3,null,5]
输出#xff1a;[1-2-5,1-3]示例…给你一个二叉树的根节点 root 按 任意顺序 返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。 示例 1
输入root [1,2,3,null,5]
输出[1-2-5,1-3]示例 2
输入root [1]
输出[1] 代码
/*** Definition for a binary树节点.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/// 定义一个常量NUM用于表示一些数组的大小等相关操作这里假设其值为100
#define NUM 100// 深度优先搜索函数用于递归地遍历二叉树构建从根节点到叶子节点的路径字符串并将这些路径存储到path数组中
// path: 二维字符数组指针用于存储从根节点到叶子节点的路径字符串
// temp: 字符数组用于临时存储从根节点到当前节点的路径上的节点值以字符形式
// cnt: 表示当前已经存储到temp数组中的节点值的数量索引
// size: 指向一个整数的指针用于记录已经存储到path数组中的路径数量同时也作为下一个要存储路径的下标
void dfs(char **path, char *temp, struct TreeNode *root, int cnt, int *size)
{// 如果当前节点为空说明已经遍历到树的底部或者传入的就是空树直接返回不进行后续操作if (root NULL) {return;}// 将当前节点的值转换为字符形式并存储到temp数组中然后更新cnt的值表示已经存储的节点值数量增加了1temp[cnt] root-val;// 判断当前节点是否为叶子节点即左右子节点都为空if (root-left NULL root-right NULL) {// 初始化用于记录已经写入路径字符串的字符长度为0int len 0;// 遍历temp数组中除了最后一个元素因为最后一个元素是当前叶子节点的值需要单独处理之外的所有元素for (int i 0; i cnt - 1; i) {// sprintf函数用于将格式化的数据写入字符串它的返回值是写入的字符总数// path[*size][len]表示获取path数组中第*size条路径字符串并将指针移动到已经写入字符的末尾位置以便后续继续拼接字符串// 将temp[i]的值格式化为字符串并拼接到path数组中第*size条路径字符串中例如将整数3格式化为3然后拼接到路径字符串中len sprintf(path[*size][len], %d-, temp[i]);}// 将当前叶子节点的值格式化为字符串并拼接到path数组中第*size条路径字符串的末尾完成整个路径字符串的拼接sprintf(path[*size][len], %d, temp[cnt - 1]);// 更新已经存储到path数组中的路径数量将*size的值加1以便下一次存储路径时使用下一个下标*size 1;// 完成当前叶子节点路径的构建和存储后返回继续处理其他节点return;}// 递归地调用dfs函数处理当前节点的左子节点继续构建从根节点到左子树叶子节点的路径dfs(path, temp, root-left, cnt, size);// 递归地调用dfs函数处理当前节点的右子节点继续构建从根节点到右子树叶子节点的路径dfs(path, temp, root-right, cnt, size);// 完成当前节点及其子节点的处理后返回继续处理其他节点return;
}/*** Note: The returned array must be malloced, assume caller calls free().*/// 函数binaryTreePaths用于获取二叉树从根节点到所有叶子节点的路径字符串数组
// root: 二叉树的根节点指针
// returnSize: 一个指针用于返回路径字符串数组的大小即存储了多少条路径字符串
char ** binaryTreePaths(struct TreeNode* root, int* returnSize)
{// 为存储路径字符串的二维字符数组分配内存空间假设最多有NUM条路径根据前面定义的常量NUMchar **path (char **)malloc(NUM * sizeof(char *));// 为二维字符数组中的每个指针所指向的字符数组分配内存空间每个字符数组假设最多能容纳NUM个字符for (int i 0; i NUM; i) {path[i] (char *)malloc(NUM * sizeof(char));}// 定义一个字符数组temp用于在dfs函数中临时存储从根节点到当前节点的路径上的节点值假设最多能容纳NUM个字符char temp[NUM];// 初始化用于记录已经存储到temp数组中的节点值的数量为0int cnt 0;// 初始化用于记录已经存储到path数组中的路径数量为0int size 0;// 调用dfs函数开始递归地构建从根节点到所有叶子节点的路径字符串并将结果存储到path数组中dfs(path, temp, root, cnt, size);// 通过returnSize指针返回存储到path数组中的路径数量*returnSize size;// 返回存储路径字符串的二维字符数组指针调用者可以通过这个指针访问路径字符串数组中的元素记得在使用完后要释放内存return path;
}
