257. 二叉树的所有路径

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/binary-tree-paths

题目：给你一个二叉树的根节点root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

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

• 示例 1：

  

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

• 示例 2：

输入：root = [1]
输出：["1"]

• 提示：
  • 树中节点的数目在范围 [1, 100] 内
  • -100 <= Node.val <= 100

C语言求解

方法一：迭代

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

void construct_paths(struct TreeNode* root, char** res, int* returnSize, int* sta, int top) {
    if (root != NULL) {
        if (root->left == NULL && root->right == NULL) {  // 当前节点是叶子节点
            char* tmp = (char*)malloc(1001);
            int len = 0;
            for (int i = 0; i < top; i++) {
                len += sprintf(tmp + len, "%d->", sta[i]);
            }
            sprintf(tmp + len, "%d", root->val);
            res[(*returnSize)++] = tmp;  // 把路径加入到答案中
        } else {
            sta[top++] = root->val;  // 当前节点不是叶子节点，继续递归遍历
            construct_paths(root->left, res, returnSize, sta, top);
            construct_paths(root->right, res, returnSize, sta, top);
        }
    }
}

char** binaryTreePaths(struct TreeNode* root, int* returnSize) {
    char** paths = (char**)malloc(sizeof(char*) * 1001);
    *returnSize = 0;
    int sta[1001];
    construct_paths(root, paths, returnSize, sta, 0);
    return paths;
}
c

方法二：广度优先

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char **binaryTreePaths(struct TreeNode *root, int *returnSize) {
    char **paths = (char **) malloc(sizeof(char *) * 1001);
    *returnSize = 0;
    if (root == NULL) {
        return paths;
    }

    struct TreeNode **node_queue = (struct TreeNode **) malloc(sizeof(struct TreeNode *) * 1001);
    char **path_queue = (char **) malloc(sizeof(char *) * 1001);

    int left = 0, right = 0;

    char *tmp = malloc(sizeof(char) * 1001);
    sprintf(tmp, "%d", root->val);
    node_queue[right] = root;
    path_queue[right++] = tmp;

    while (left < right) {
        struct TreeNode *node = node_queue[left];
        char *path = path_queue[left++];

        if (node->left == NULL && node->right == NULL) {
            paths[(*returnSize)++] = path;
        } else {
            if (node->left != NULL) {
                tmp = malloc(sizeof(char) * 1001);
                sprintf(tmp, "%s->%d", path, node->left->val);
                node_queue[right] = node->left;
                path_queue[right++] = tmp;
            }

            if (node->right != NULL) {
                tmp = malloc(sizeof(char) * 1001);
                sprintf(tmp, "%s->%d", path, node->right->val);
                node_queue[right] = node->right;
                path_queue[right++] = tmp;
            }
        }
    }
    return paths;
}
c

微信原创文章

2022-09.19 ​257.二叉树的所有路径

2022-08-13 ​Arduino使用红外遥控控制8×8点阵显示

2022-08-12 Arduino使用蓝牙控制8×8点阵显示

2022-08-10 Arduino控制8×8点阵显示

2022-05-14 收集几个前后端网站

2022-05-06 前端选择本地图片并压缩

2022-05-05 前端选择本地文件并显示

2022-05-01 写了一个很简易的Markdown编辑器