使用c++代码实现求解二叉树所有路径
时间: 2023-03-31 18:01:18 浏览: 72
可以使用递归的方式来实现求解二叉树所有路径的功能。具体实现方法如下:
1. 定义一个函数,输入参数为当前节点指针、当前路径字符串和结果数组。
2. 如果当前节点为空,则直接返回。
3. 将当前节点的值添加到当前路径字符串中。
4. 如果当前节点为叶子节点,则将当前路径字符串添加到结果数组中。
5. 否则,递归遍历当前节点的左子树和右子树,分别调用上述函数。
6. 递归结束后,将当前节点的值从当前路径字符串中删除,以便遍历其它路径。
下面是具体的 C 代码实现:
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_PATH_LEN 100
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
void binaryTreePathsHelper(struct TreeNode* node, char* path, char** result, int* returnSize) {
if (node == NULL) {
return;
}
int len = strlen(path);
if (len > ) {
path[len] = '-';
path[len+1] = '>';
path[len+2] = '\';
}
char val_str[10];
sprintf(val_str, "%d", node->val);
strcat(path, val_str);
if (node->left == NULL && node->right == NULL) {
result[*returnSize] = (char*)malloc(sizeof(char) * (strlen(path) + 1));
strcpy(result[*returnSize], path);
(*returnSize)++;
} else {
binaryTreePathsHelper(node->left, path, result, returnSize);
binaryTreePathsHelper(node->right, path, result, returnSize);
}
path[strlen(path) - strlen(val_str) - 2] = '\';
}
char ** binaryTreePaths(struct TreeNode* root, int* returnSize) {
char** result = (char**)malloc(sizeof(char*) * MAX_PATH_LEN);
*returnSize = ;
char path[MAX_PATH_LEN];
path[] = '\';
binaryTreePathsHelper(root, path, result, returnSize);
return result;
}
int main() {
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = 1;
root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->left->val = 2;
root->left->left = NULL;
root->left->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->left->right->val = 5;
root->left->right->left = NULL;
root->left->right->right = NULL;
root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->right->val = 3;
root->right->left = NULL;
root->right->right = NULL;
int returnSize;
char** result = binaryTreePaths(root, &returnSize);
for (int i = ; i < returnSize; i++) {
printf("%s\n", result[i]);
}
return ;
}
```
运行结果如下:
```
1->2->5
1->3
```