数据结构——二叉树的最小深度算法-蒲公英云

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

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

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

说明：叶子节点是指没有子节点的节点。
在这里插入图片描述
输入：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.二叉树的最小深度

思路：
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);
 }