二叉樹的所有路徑

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

題目：給你一個二叉樹的根節(jié)點root，按任意順序，返回所有從根節(jié)點到葉子節(jié)點的路徑。

葉子節(jié)點是指沒有子節(jié)點的節(jié)點。

示例 1：

e.g.

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

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

示例 2：

輸入：root = [1]

輸出：["1"]

提示：

-100 <= Node.val <= 100

樹中節(jié)點的數(shù)目在范圍[1, 100]內(nèi)

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) { // 當(dāng)前節(jié)點是葉子節(jié)點

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; // 當(dāng)前節(jié)點不是葉子節(jié)點，繼續(xù)遞歸遍歷

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;

}

方法二：廣度優(yōu)先

/**

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

}

編輯：黃飛