网站可以换域名吗,关键词优化网站,php 网站 整合 数据库,百度推广网址是多少给定一个二叉树#xff0c;找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明#xff1a;叶子节点是指没有子节点的节点。 输入#xff1a;root [3,9,20,null,null,15,7] 输出#xff1a;2 示例 2#xff1a;
输入#xff1a;root …给定一个二叉树找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明叶子节点是指没有子节点的节点。 输入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 #includestdio.h
#includebits/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#)TNULL;else {T(BiNode*)malloc(sizeof(BiNode));if(!T)exit(-1);T-datach;CreateBiTree(T-lchild);CreateBiTree(T-rchild);}
}void DestroyBiTree(BiTree T)//二叉树的销毁算法
{if(TNULL)exit(-1);else{DestroyBiTree(T-lchild);DestroyBiTree(T-rchild);free(T);}
}int preorderTraverse(BiTree T)//二叉树的先序递归遍历算法
{if(TNULL)return 0;else {printf(%c ,T-data);preorderTraverse(T-lchild);preorderTraverse(T-rchild);}} int InorderTraverse(BiTree T)//二叉树的中序递归遍历算法
{if(TNULL)return 0;else {InorderTraverse(T-lchild);printf(%c ,T-data);InorderTraverse(T-rchild);}}int PostorderTraverse(BiTree T)//二叉树的后序递归遍历算法
{if(TNULL)return 0;else {PostorderTraverse(T-lchild);PostorderTraverse(T-rchild);printf(%c ,T-data);}}
int minDepth(BiTree T)//求二叉树的最小深度算法
{int depth10,depth20,depth0;if(TNULL) return 0;if(T-lchildNULLT-rchildNULL) return 1;if(T-lchild!NULLT-rchildNULL) {depth1minDepth(T-lchild);return depth11;}if(T-lchildNULLT-rchild!NULL) {depth2minDepth(T-rchild);return depth21;}if(T-lchildNULLT-rchildNULL){depth1minDepth(T-lchild);depth2minDepth(T-rchild);}if(depth1depth2)depthdepth1;else depthdepth2;return depth1;} 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);}
