专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

据华为内部通报，在外包招聘过程中，多名产品线负责人存在自身参与替考、安排别人代考、向候选人泄题等违规行为；还有多人存在通过出卖公司信息资产获利的情况。经研究，对涉事人员予以开除，并要求其退回非法获利、赔偿公司损失。

据网传聊天截图显示，招一个人可以拿2W内推费，然后这边hr说包进od。公司这边帮忙捞人，协助作弊，有代考，泄题，写好面评。入职之后一个月收两千，也就是说，每个外包，至少能薅2万，如果入职之后，每月还能持续薅2000元。截图称共裁了100多个od（外包），光内推费就已经超200万元，而实际可能更高。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第111题：二叉树的最小深度。

问题描述

来源：LeetCode第111题

难度：简单

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例1：

输入：root = [3,9,20,null,null,15,7] 输出：2

示例2：

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

  • 树中节点数的范围在 [0, 10^5] 内

  • -1000 <= Node.val <= 1000

问题分析

这题让计算二叉树的最小深度，也就是从根节点到最近的叶子节点，比较简单。常见的有两种实现方式，一种是使用BFS，也就是一层一层的遍历，当遍历到第一个叶子节点的时候，它所在的层数就是二叉树的最小深度。

还一种是使用递归的方式，如果左子树为空，则计算右子树的深度，如果右子树为空，则计算左子树的深度，如果左右子树都不为空，则取左右子树深度的最小值加 1 。

JAVA：

public int minDepth(TreeNode root) {     if (root == null)         return 0;     // 如果左子树等于空，返回右子树的最小高度+1     if (root.left == null)         return minDepth(root.right) + 1;     // 如果右子树等于空，返回左子树的最小高度+1     if (root.right == null)         return minDepth(root.left) + 1;     // 如果左右子树都不为空，返回左右子树深度最小的那个+1     return Math.min(minDepth(root.left), minDepth(root.right)) + 1; }

C++：

public:     int minDepth(TreeNode *root) {         if (root == nullptr)             return 0;         // 如果左子树等于空，返回右子树的最小高度+1         if (root->left == nullptr)             return minDepth(root->right) + 1;         // 如果右子树等于空，返回左子树的最小高度+1         if (root->right == nullptr)             return minDepth(root->left) + 1;         // 如果左右子树都不为空，返回左右子树深度最小的那个+1         return min(minDepth(root->left), minDepth(root->right)) + 1;     }

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。