二叉树最小深度
参考链接：https://www.nowcoder.com/questionTerminal/e08819cfdeb34985a8de9c4e6562e724?f=discussion
题目描述
求给定二叉树的最小深度。最小深度是指树的根结点到最近叶子结点的最短路径上结点的数量。
基本思路
- 递归思路：
递归，若为空树返回0；
若左子树为空，则返回右子树的最小深度+1；（加1是因为要加上根这一层，下同）
若右子树为空，则返回左子树的最小深度+1；
若左右子树均不为空，则取左、右子树最小深度的较小值，+1；
- 非递规思路：
利用队列采用层序遍历，一旦找到一个叶节点，它肯定是最短的。
代码如下
//递归实现 int DepTreeMinPath(TreeNode *root) { if(root == NULL){ return 0; } if(root->left == NULL){ //如果左子树为空，则返回右子树的最小深度+1 return DepTreeMinPath(root->right) + 1; } else if(root->right == NULL){ //如果右子树为空，则返回左子树的最小深度+1 return DepTreeMinPath(root->left) + 1; } //左右子树都不为空，则取较小值 int LeftHeight = DepTreeMinPath(root->left); int RightHeight = DepTreeMinPath(root->right); return LeftHeight > RightHeight ? (RightHeight + 1) : (LeftHeight + 1); }
