求给定二叉树的最小深度。最小深度是指树的根结点到最近叶子结点的最短路径上结点的数量。
[编程题]二叉树的最小深度
public class Solution {
public int run(TreeNode root) {
if(root == null){
return 0;
}
// 只有单个子树的情况
if (null == root.left){
return run(root.right) + 1;
}
if (null == root.right){
return run(root.left) + 1;
}
// 双子树情况
return Math.min(run(root.left), run(root.right)) + 1;
}
}
注：求二叉树的最大深度时，只需要考虑节点左右子树的最大值即可，单子树的情况不需要考虑；而二叉树的最小深度，当只有单个子时，子树深度就是最小深度，所以此种情况需要考虑，否则会出现深度为0的问题。
发表于 2016-08-09 22:49:26
回复(0)
import sys sys.setrecursionlimit(1000000) class Solution: def run(self , root): if root is None: return 0 if root.left is None and root.right is None: return 1 if root.left is None: return 1 + self.run(root.right) if root.right is None: return 1 + self.run(root.left); return 1 + min(self.run(root.left), self.run(root.right))
发表于 2021-07-21 10:02:23
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型
*/
int depth = 0;
public int run (TreeNode root) {
// write code here
if(root == null) {
return depth;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
run(queue);
return depth;
}
public void run(Queue<TreeNode> queue) {
int qsize = queue.size();
if(qsize>0) {
depth++;
}else {
return ;
}
while(qsize>0) {
TreeNode node = queue.poll();
System.out.println(node.val);
qsize--;
if(node.left == null && node.right == null) {
return;
}
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
}
run(queue);
}
} 解题思路：利用队列实现广度优先搜索叶子节点（没有子节点的节点，left==null和right==null）
发表于 2021-03-26 10:27:07
回复(0)
class Solution {
public:
int run(TreeNode* root) {
if(root == nullptr) return 0;
queue<TreeNode*> q; q.push(root);
int dep = 1;
while(!q.empty())
{
int s = q.size();
while(s--)
{
TreeNode* t = q.front(); q.pop();
if(t->right == nullptr && t->left == nullptr) return dep;
if(t->right) q.push(t->right);
if(t->left) q.push(t->left);
}
dep++;
}
return dep;
}
};
发表于 2021-01-24 21:27:59
回复(0)
DFS深搜。全局变量mindeepth记录最小深度，遇到左右子树皆为NULL的叶子节点时，更新之
注意，判断空树
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类
* @return int整型
*/
int mindeepth = INT_MAX;
void dfs(TreeNode* root, int deepth) {
if (root == NULL) { return ; }
if (root->left == NULL && root->right == NULL) {
if (deepth < mindeepth) {
mindeepth = deepth;
}
}
dfs(root->left, deepth +
1);
dfs(root->right, deepth + 1);
}
int run(TreeNode* root) {
dfs(root, 1) ;
return mindeepth == INT_MAX ? 0 : mindeepth;
}
};
发表于 2020-12-28 15:58:26
回复(0)
int run(TreeNode* root) {
// write code here
if(root==NULL) return 0;
if(root->left==NULL&&root->right==NULL) return 1;
if(root->left==NULL&&root->right!=NULL) return 1+run(root->right);
if(root->left!=NULL&&root->right==NULL) return 1+run(root->left);
if(root->left!=NULL&&root->right!=NULL) return min(1+run(root->left),1+run(root->right));
}
编辑于 2020-08-07 14:37:06
回复(0)
这道题和leetcode104不能弄混，这道题是“树的根结点”到”最近叶子结点“的最短路径上结点的数量。不是简单求个最小深度，因此在一棵树上有一端是空另一端不空的情况下，应该返回有非空的那一边的深度。
原本leetcode104的代码，在这里不能通过：
public static int getMinDepth(Node node) {
if (node == null) {
return 0;
}
int leftDepth = getMinDepth(node.left) + 1;
int rightDepth = getMinDepth(node.right) + 1;
return Math.min(leftDepth, rightDepth);
} 修改后 public class Solution {
public int run(TreeNode root) {
if(root==null){
return 0;
}
int left = run(root.left);
int right = run(root.right);
if(left*right >0){//判断，如果有一端是空，是返回数字大的非空一段，因为是求到叶子节点的距离
return (left>right?right:left)+1;
}else{
return (left>right?left:right)+1;
}
}
}
编辑于 2020-04-30 01:57:57
回复(0)
思路1：递归
若空树，则返回0
若左子树为空，则返回右子树最小深度+1
若右子树为空，则返回左子树最小深度+1
若左右子树均不为空，则返回左右子树较小者+1
import java.lang.Math;
public class Solution {
public int run(TreeNode root) {
//若空树，则返回0
if(root == null) return 0;
//若左子树为空，则返回右子树最小深度+1
if(root.left==null) return run(root.right)+1;
//若右子树为空，则返回左子树最小深度+1
if(root.right==null) return run(root.left)+1;
//若左右子树均不为空，则返回左右子树较小者+1
return (Math.min(run(root.left),run(root.right))+1);
}
} 思路2：层次遍历
若为空树，返回0
声明队列，头结点入队
声明深度记录变量depth
--------
若队列非空，每次处理一层的节点（即使用for循环来实现该处理）下一层节点进入队列。
判断条件：当出现节点左右子树均为空时，则此时的层数记为最短路径长。
否则，左子树、右子树进队
--------
*/
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
public int run(TreeNode root) {
if(root == null) return 0;//若为空树，返回0
if(root.left==null && root.right==null) return 1;
//声明队列，声明深度记录变量
Queue<TreeNode> queue = new LinkedList<>();
//声明队列，头结点入队
queue.offer(root);
//声明深度记录变量depth
int depth = 0;
while(!queue.isEmpty()){
int len = queue.size();
depth++;
//若队列非空，每次处理一层的节点（即使用for循环来实现该处理）下一层节点进入队列。
for(int i=0;i<len;i++){
TreeNode curNode = queue.poll();
//判断条件：当出现节点左右子树均为空时，则此时的层数记为最短路径长。
if(curNode.left==null && curNode.right==null) return depth;
//左子树非空，左子树进队
if(curNode.left != null) queue.offer(curNode.left);
//右子树非空，右子树进队
if(curNode.right != null) queue.offer(curNode.right);
}
}
return 0;
}
}
发表于 2020-04-22 22:05:03
回复(0)
非递归思路写法，简单易懂，进行二叉树的层数遍历，当找到第一个叶子节点是返回其深度。
class Solution {
public:int run(TreeNode *root) {
if(root==nullptr)
{
return 0;
}
int num=1;
TreeNode *last=root; //本层的最后一个节点
TreeNode *nlast=NULL; //下一层最后一个节点
queue<TreeNode*> q;
q.push(root);
//结束条件为左右节点都为空节点
while(!q.empty())
{
TreeNode *pi=q.front();
q.pop();
if(pi->left==NULL&&pi->right==NULL)//结束条件，第一个叶子节点
{
return num;
}
if(pi->left!=NULL)
{
q.push(pi->left);
nlast=pi->left;
}
if(pi->right!=NULL)
{
q.push(pi->right);
nlast=pi->right;
}
if(pi==last) //本层的节点数遍历到最后一个了，更新last
{
last=nlast;
num++;
}
}
}
};
发表于 2020-01-09 17:13:02
回复(0)
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int run(TreeNode root) {
if(root==null)
return 0;
if(root.left == null && root.right == null)
return 1;
if(root.left != null && root.right != null)
return min(run(root.left),run(root.right))+1;
return max(run(root.left),run(root.right))+1;
}
public int min(int a,int b){
return a > b ? b : a;
}
public int max(int a,int b){
return a > b ? a : b;
}
}
java递归解决，遇到空值返回0，遇到叶子节点返回1，遇到只有一个子节点的，则继续沿着子节点递归，直到遍历至叶子节点
发表于 2019-10-22 11:30:53
回复(0)
方法1：递归
思路：每个结点都有三种情况
1.不存在左右孩子，此时就找到了最小深度，返回即可
2.存在左孩子或存在右孩子
2.1存在左孩子，需要查找右孩子的最大深度
2.2存在右孩子，需要查找左孩子的最大深度
3.存在左孩子和右孩子，需要查找左孩子和右孩子之间的较小值
代码实现：
public class Solution {
public int run(TreeNode root) {
if(root==null) return 0;
if(root.left==null && root.right==null) return 1;
if(root.left==null || root.right==null) return Math.max(run(root.left),run(root.right))+1;
return Math.min(run(root.left),run(root.right))+1;
} 方法2：非递归
思路：层次遍历，找到第一个无左右孩子的结点
每次遍历并取出队列中的首位元素，并执行如下操作：
1.如果不存在左右孩子，此时找到了最小深度，返回即可
2.存在左孩子或存在右孩子
2.1存在左孩子，需要将左孩子入队
2.2存在右孩子，需要将右孩子入队
深度加1，然后重复上述步骤
代码如下：
import java.util.*;
public class Solution {
public int run(TreeNode root) {
if(root==null) return 0;
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
int depth=1;
while(!queue.isEmpty()){
int size=queue.size();
for(int i=0;i<size;i++){
TreeNode node=queue.poll();
if(node.left==null && node.right==null) return depth;
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
}
depth++;
}
return depth;
}
}
发表于 2019-10-21 11:28:47
回复(0)
3年多没写 C++ 了，感觉好多语法都得网上查，要清楚一点，叶子几点是左右子树都为空的节点。
递归遍历，获取每个节点左右子树的最小深度
class Solution {
public:
int run(TreeNode *root) {
if(root == NULL){
return 0;
}else if(root->left and root->right){
return min(run(root->left), run(root->right)) + 1;
}else if(root->left){
return run(root->left) + 1;
}else if(root->right){
return run(root->right) + 1;
}
}
}; 层次遍历，从上往下一层一层的找，一旦找到就停止
class Solution {
public:
int run(TreeNode *root) {
if(root == NULL){
return 0;
}
queue<TreeNode *> q1;
int level = 0;
q1.push(root);
while(q1.size() != 0){
level++;
queue<TreeNode *> q2;
while(q1.size() != 0){
TreeNode* node1 = q1.front();
q1.pop();
if(!node1->left and !node1->right){
return level;
}else{
if(node1->left){
q2.push(node1->left);
}
if(node1->right){
q2.push(node1->right);
}
}
}
q1 = q2;
}
return level;
}
};
编辑于 2019-10-01 11:01:46
回复(0)
// BFS，层序遍历,找到第一个叶子节点的层数
class Solution {
public:
int minDepth(TreeNode* root) {
if(root == NULL)
return 0;
queue<TreeNode*> que;
que.push(root);
int depth = 0;
while(!que.empty())
{
int size = que.size();
depth++;
for(int i = 0; i < size; ++i)
{
TreeNode* tmp = que.front();
if(tmp->left != NULL)
que.push(tmp->left);
if(tmp->right != NULL)
que.push(tmp->right);
que.pop();
// 找到第一个叶子节点，返回
if(tmp->left == NULL && tmp->right == NULL)
return depth;
}
}
return -1;
}
};
// 递归
class Solution {
public:
int minDepth(TreeNode* root) {
if(root == NULL)
return 0;
int left = minDepth(root->left);
int right = minDepth(root->right);
return (min(left, right) ? min(left, right) : max(left, right)) + 1;
}
};
发表于 2019-08-22 11:10:34
回复(0)
运用好递归思想和深入了解二叉树的原理就不是那么难。public class Solution { public int run(TreeNode root) {// 递归结束条件 if(root == null){ return 0; }// 获取左子树的深度 int lDepth = run(root.left);// 获取右子树的深度 int rDepth = run(root.right);// 对没有孩子的结点进行判断 if(lDepth + rDepth == 0){ return 1; }// 对只有一个孩子的结点进行判断 if(lDepth * rDepth == 0){ return lDepth + rDepth + 1; }// 对左右子树深度进行最小值求取 return Math.min(lDepth, rDepth) + 1; } }
发表于 2019-07-09 19:42:31
回复(0)
//递归
public class Solution {
public int run(TreeNode root) {
if(root==null){
return 0;
}
int left = run(root.left);
int right = run(root.right);
if(left !=0 && right !=0) {
return (left > right ? right : left) + 1;
}else{
return (left > right ? left : right) + 1;
}
}
}
发表于 2019-05-14 14:32:53
回复(1)
题目描述
Given a binary tree, find its minimum depth.The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
解题思路
解决树的问题，递归肯定是最简单的代码。我们之前练习过求树的最大深度，但是要注意，求最小深度和最大深度是稍微有点不一样的，因为最大深度只需要考虑哪边大即可，即使是单子树（树只有一侧有结点），方式与求双子树的最大深度是一样的。但是对于求最小深度而言，如果出现单子树的情况，那么按照最小深度的定义：根结点到叶子结点的最小距离，那么显然这个最小深度是表示有结点的那一侧。
提交代码
public class Solution {
public int run(TreeNode root) {
//递归出口条件1
if(root == null){
return 0;
}
//递归出口条件2
if(root.left == null && root.right == null){
return 1;
}
//注意点是要考虑是单子树的情况，因为很有可能只有一侧有节点，那么最小深度就是这以一侧
if(root.left == null){
return run(root.right)+1;
}
if(root.right == null){
return run(root.left)+1;
}
//如果是双子树，则对比树两边谁小即可，与求最大深度一样
return Math.min(run(root.left),run(root.right))+1;
}
}
发表于 2019-03-20 11:07:57
回复(0)
非递归实现，采用层次遍历的方法，找到第一个叶子节点的深度即为最小深度
int minDepth(TreeNode* root) //二叉树最小深度非递归实现
{
TreeNode *p = root;
queue<TreeNode*> q;
int depth = 0;
if (p == NULL) return 0;
q.push(p);
while (!q.empty())
{
depth++;
int curr = 0, size = q.size();
while (curr < size)
{
curr++;
p = q.front();
q.pop();
if (p->left != NULL) q.push(p->left);
if (p->right != NULL) q.push(p->right);
if (p->left == NULL && p->right == NULL) return depth;
}
}
return depth;
}
发表于 2019-02-26 20:34:54
回复(0)
public class Solution {
public int run(TreeNode root) {
if(root!=null){
int left = run(root.left);
int right = run(root.right);
if(left==0)
return right+1;
else if(right==0)
return left+1;
else if(left==0&&right==0)
return 1;
else
return left < right ? left+1 : right+1;
}
return 0;
}
}
发表于 2019-01-19 18:49:05
回复(0)
问题信息
难度：
472条回答
1586收藏
71808浏览
通过挑战的用户
查看代码-
2023-03-14 16:35:56
-
2023-03-06 10:12:50 -
2023-02-16 19:57:33
-
2023-02-14 17:38:07 -
2023-02-09 16:59:32
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
