数据结构——从叶子结点到根节点的全部路径

古城微笑少年丶 2022-12-24 05:49 143阅读 0赞

#### 问题 ####

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center]

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/binary-tree-paths  
[ 257.二叉树的所有路径][257.]

与此问题类似的问题  
[数据结构——二叉树的最长路径问题][Link 1]

思路：

1.  遇到的是叶子结点，将当前结点输出（也就不需要进入数组了），并将数组的元素逆序输出。
2.  遇到的不是叶子结点，将该元素进入数组。递归实现左右子树。  
    核心代码

void leaf_root(BiTree T,int *path,int len)
    {
        
    	if(T)
    	{
        
    		if(T->lchild==NULL&&T->rchild==NULL)//当T为叶子结点时，逆序输出 
    		{
        
    			printf("%c->",T->data);
    			for(int i=len-1;i>0;i--)
    			{
        
    				printf("%c->",path[i]);
    			}
    			printf("%c",path[0]);
    			printf("\n"); 
    		 
    		}
    		else//当不为终端结点时，该节点对应的值进入数组 
    		{
        
    			path[len++]=T->data;
    			leaf_root(T->lchild,path,len);
    			leaf_root(T->rchild,path,len);
    		}
    		 
    	} 
    	
    }

全部代码（可以直接运行）

#include<stdio.h>
    #include<bits/stdc++.h> 
    #define MAX  200
    typedef char TElemType;
    typedef int status; 
    typedef struct BiNode
    {
        
    	TElemType data;
    	struct BiNode *lchild;
    	struct BiNode *rchild;
    }BiNode,*BiTree;
    void CreateBiTree(BiTree &T)//二叉树的先序创建 
    {
        
    	TElemType ch;
    	scanf("%c",&ch);
    	if(ch=='#')
    		T=NULL;
    	else 
    	{
        
    		T=(BiNode*)malloc(sizeof(BiNode));
    		if(!T)
    			exit(-1);
    		T->data=ch;
    		CreateBiTree(T->lchild);
    		CreateBiTree(T->rchild);
    	}
    }
    void leaf_root(BiTree T,int *path,int len)
    {
        
    	if(T)
    	{
        
    		if(T->lchild==NULL&&T->rchild==NULL)//当T为叶子结点时，逆序输出 
    		{
        
    			printf("%c->",T->data);
    			for(int i=len-1;i>0;i--)
    			{
        
    				printf("%c->",path[i]);
    			}
    			printf("%c",path[0]);
    			printf("\n"); 
    		 
    		}
    		else//当不为终端结点时，该节点对应的值进入数组 
    		{
        
    			path[len++]=T->data;
    			leaf_root(T->lchild,path,len);
    			leaf_root(T->rchild,path,len);
    		}
    		 
    	} 
    	
    } 
    int main()
    {
        
    	BiTree T;
    	printf("创建树输入树T的先序序列(其中使用#代表空节点)\n");
    	CreateBiTree(T);
    	int path[MAX]={
        0};
    
    	int len=0;
    	printf("输出全部从叶子结点到根节点的路径：\n"); 
    	leaf_root(T,path,len);
    	
    	
    
    	
    	
    }

![在这里插入图片描述][2020112622103347.png_pic_center]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/fc448211671240fc9885b1c948ec25b5.png
[257.]: https://leetcode-cn.com/problems/binary-tree-paths/
[Link 1]: https://blog.csdn.net/qq_50675813/article/details/110204845
[2020112622103347.png_pic_center]: /images/20221120/0ad3744f435b4d07afa966b1fc5ed7fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/128de306d23c4014b2fd750a7f61671b.png