力扣257：二叉树的所有路径

时间：2024-11-16 08:38:02

给你一个二叉树的根节点 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的值，表示已经存储的节点值数量增加了1
    temp[cnt++] = root->val;

    // 判断当前节点是否为叶子节点，即左右子节点都为空
    if (root->left == NULL && root->right == NULL) {

        // 初始化用于记录已经写入路径字符串的字符长度为0
        int 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条路径（根据前面定义的常量NUM）
    char **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数组中的节点值的数量为0
    int cnt = 0;

    // 初始化用于记录已经存储到path数组中的路径数量为0
    int size = 0;

    // 调用dfs函数开始递归地构建从根节点到所有叶子节点的路径字符串，并将结果存储到path数组中
    dfs(path, temp, root, cnt, &size);

    // 通过returnSize指针返回存储到path数组中的路径数量
    *returnSize = size;

    // 返回存储路径字符串的二维字符数组指针，调用者可以通过这个指针访问路径字符串数组中的元素，记得在使用完后要释放内存
    return path;
}

相关文章