数据结构——二叉树的最小深度算法

今天药忘吃喽~ 2022-12-23 09:41 163阅读 0赞

##### 给定一个二叉树，找出其最小深度。 #####

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center]  
输入：root = \[3,9,20,null,null,15,7\]  
输出：2  
示例 2：

输入：root = \[2,null,3,null,4,null,5,null,6\]  
输出：5

提示：

树中节点数的范围在 \[0, 105\] 内  
\-1000 <= Node.val <= 1000

来源：力扣（LeetCode）  
[111.二叉树的最小深度][111.]

思路：  
1.如果T（根节点）为空，返回**0**；  
2.如果T的左右子树都为空，返回**1**；  
3.如果T->lchild不为空且T->rchild为空，返回**左子树的高度+1**；  
4.如果T->lchild为空且T->rchild不为空，返回**右子树的高度+1**；  
如果T->lchild不为空且T->rchild不为空，即左右子树都不为空，返回**min（左子树的高度+1,右子树的高度+1）**；

#include<stdio.h>
    #include<bits/stdc++.h> 
    
    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 DestroyBiTree(BiTree &T)//二叉树的销毁算法 
    {
        
    	if(T==NULL)
    		exit(-1);
    	else
    	{
        
    		DestroyBiTree(T->lchild);
    		DestroyBiTree(T->rchild);
    		free(T);
    	}
    }
    
    int  preorderTraverse(BiTree T)//二叉树的先序递归遍历算法 
    {
        
    	if(T==NULL)
    		return 0;
    	else 
    		{
        
    			printf("%c ",T->data);
    			preorderTraverse(T->lchild);
    			preorderTraverse(T->rchild);
    		}
     } 
     
    int  InorderTraverse(BiTree T)//二叉树的中序递归遍历算法 
    {
        
    	if(T==NULL)
    		return 0;
    	else 
    		{
        
    			InorderTraverse(T->lchild);
    			printf("%c ",T->data);
    			InorderTraverse(T->rchild);
    		}
     }
     
    int  PostorderTraverse(BiTree T)//二叉树的后序递归遍历算法 
    {
        
    	if(T==NULL)
    		return 0;
    	else 
    		{
        
    			PostorderTraverse(T->lchild);
    			PostorderTraverse(T->rchild);
    			printf("%c ",T->data);
    		}
     }
    int  minDepth(BiTree T)//求二叉树的最小深度算法 
    {
        
    	int depth1=0,depth2=0,depth=0;
    	if(T==NULL) return 0;
    	if(T->lchild==NULL&&T->rchild==NULL) return 1;
    	if(T->lchild!=NULL&&T->rchild==NULL) 
    	{
        
    		depth1=minDepth(T->lchild);
    		return depth1+1;
    	}
    	
    	if(T->lchild==NULL&&T->rchild!=NULL) 
    	{
        
    		depth2=minDepth(T->rchild);
    		return depth2+1;
    	}
    	if(T->lchild==NULL&&T->rchild==NULL)
    	{
        
    		depth1=minDepth(T->lchild);
    		depth2=minDepth(T->rchild);
    	}
    	
    	if(depth1<depth2)
    			depth=depth1;
    	else 	depth=depth2;
    	
    	
    	return depth+1;
     } 
    
    
    int main()
    {
        
    	BiTree T;
    	printf("创建树输入树T的先序序列(其中使用#代表空节点)\n");
    	CreateBiTree(T);
    	
    	printf("求树的最小深度算法\n");
    	printf("树的最小深度为：%d\n",minDepth(T));
    	
    	printf("先序遍历算法");
    	preorderTraverse(T);
    	printf("\n中序遍历算法");
    	InorderTraverse(T);
    	printf("\n后序遍历算法");
    	PostorderTraverse(T);
     }

![在这里插入图片描述][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/79e0cafecd31497ab3877d7359625a1c.png
[111.]: https://leetcode-cn.com/problems/minimum-depth-of-binary-tree
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/7cd58163425e4314aae5740748cd13ee.png