前言
题目链接
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
一、深度优先
1.1 算法概述
深度优先搜索属于图算法的一种，英文缩写为DFS。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
深度优先搜索是一种在开发爬虫早期使用较多的方法，它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。
它的思想：
a.访问顶点v；
b.依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
c.若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。
1.2 原理详解
深度优先搜索用栈（stack）来实现，整个过程可以想象成一个倒立的树形:
1、把根节点压入栈中。
2、每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。
3、找到所要找的元素时结束程序。
4、如果遍历整个树还没有找到，结束程序。
1.3 代码
/*** Definition for a binary tree node.* struct TreeNode {*int val;*struct TreeNode *left;*struct TreeNode *right;* };*///深度优先int minDepth(struct TreeNode* root){if(!root) return 0;if(!root->left && !root->right) return 1;int min_dep = pow(2, sizeof(min_dep) * 8) - 1;if(root->left){int tmp = minDepth(root->left);min_dep = tmp < min_dep ? tmp : min_dep;}if(root->right){int tmp = minDepth(root->right);min_dep = tmp < min_dep ? tmp : min_dep;}return min_dep + 1;}
二、广度优先
2.1 算法概述
宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
2.2 原理详解
广度优先搜索使用队列（queue）来实现，整个过程也可以看做一个倒立的树形：
1、把根节点放到队列的末尾。
2、每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。
3、找到所要找的元素时结束程序。
4、如果遍历整个树还没有找到，结束程序。
2.3 代码
//广度优先/*** Definition for a binary tree node.* struct TreeNode {*int val;*struct TreeNode *left;*struct TreeNode *right;* };*/typedef struct queue_node{struct queue_node* next;struct TreeNode* val;int dep;}queue_node_t;queue_node_t* init_queue_node(struct TreeNode* tree_node, int depth){queue_node_t* node = (queue_node_t*)malloc(sizeof(*node));node->next = NULL;node->val = tree_node;node->dep = depth;return node;}int minDepth(struct TreeNode* root){if(!root) return 0;if(!root->left && !root->right) return 1;int res = 0;queue_node_t* tail = NULL, *iter = NULL, *new_node = NULL;queue_node_t* head = init_queue_node(root, 1);iter = head;tail = head;while(iter){res = iter->dep;if(!iter->val->left && !iter->val->right){break;}if(iter->val->left){new_node = init_queue_node(iter->val->left, iter->dep + 1);tail->next = new_node;tail = tail->next;}if(iter->val->right){new_node = init_queue_node(iter->val->right, iter->dep + 1);tail->next = new_node;tail = tail->next;}iter = iter->next;}return res;}
如果觉得《算法 二叉树的最小深度（深度优先（递归栈stack）/广度优先（队列queue））》对你有帮助，请点赞、收藏，并留下你的观点哦！
