输出二叉树的所有路径-c语言dfs
这个题目还是很有趣的叭，甚至可以说很实用的一个题目了，大家感兴趣可以学习一下
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3,null,5]
输出：[“1->2->5”,“1->3”]
示例 2：
输入：root = [1]
输出：[“1”]
代码实现如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int len(int a){
int s=0;
int n=abs(a);
while(n){
n=n/10;
s++;
}
return s;
}
void dfs(struct TreeNode* root ,int size,char ** s,int po,int *returnSize){
int c;
int j;
if(size>*returnSize){
*returnSize=size;
}
if(root){
if(s[size][0]!='\0'){
// printf("df1");
s[size][po]='-';
s[size][po+1]='>';
}
if(po==1&&s[size][0]=='\0'){
po=po-3;
}
int length=len(root->val);
int n=abs(root->val);
int i=1;
if(root->val<0){
length=length+1;
}
while(n){
// printf("df2");
c=n%10;
n=n/10;
s[size][po+length+i]=0x30+c;
i--;
}
if(root->val<0){
s[size][po+length+i]='-';
}
if(root->left&&root->right){
dfs(root->left,size,s,po+length+2,returnSize);
(*returnSize)++;
for(j=0;j<po+length+2;j++){
s[*returnSize][j]=s[size][j];
}
dfs(root->right,*returnSize,s,po+length+2,returnSize);
}
if(root->left&&root->right==NULL){
dfs(root->left,size,s,po+length+2,returnSize);
}
if(root->left==NULL&&root->right){
dfs(root->right,size,s,po+length+2,returnSize);
}
if(root->left==NULL&&root->right==NULL){
s[size][po+length+2]='\0';
}
}
else{
s[size][po]='\0';
}
}
// ["1->2->5","1->3"]
//["1->2->5","1->3"]
char ** binaryTreePaths(struct TreeNode* root, int* returnSize){
char ** s=(char **)malloc(sizeof(char *)*100);
int i=0;
for(i=0;i<100;i++){
s[i]=(char *)malloc(sizeof(char)*100);
s[i][0]='\0';
}
*returnSize=0;
dfs(root,0,s,1,returnSize);
(*returnSize)++;
// printf("df3");
printf("%d ",*returnSize);
return s;
}
