专栏: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算法文档 。
特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.