二叉树按任意顺序，返回所有路径程序实现

西西 2022-09-20 888

电子说

1.3w人已加入

描述

二叉树的所有路径

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

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

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

示例 1：

二叉树

e.g.

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

输出：["1->2->5","1->3"]

示例 2：

输入：root = [1]

输出：["1"]

提示：

-100 <= Node.val <= 100

树中节点的数目在范围 [1, 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;

}

方法二：广度优先

/**

* 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;

}

编辑：黄飞

打开APP阅读更多精彩内容