求给定二叉树的最小深度。最小深度是指树的根结点到最近叶子结点的最短路径上结点的数量。
[编程题]二叉树的最小深度
来个非递归的，思路是层序遍历，找到第一个左右结点都为null的情况，就返回
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
public int run(TreeNode root) {
if(root == null)
return 0;
if(root.left == null && root.right == null)
return 1;
int depth = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int len = queue.size();
depth++;
for(int i = 0; i < len; i++){
TreeNode cur = queue.poll();
if(cur.left == null && cur.right == null)
return depth;
if(cur.left != null)
queue.offer(cur.left);
if(cur.right != null)
queue.offer(cur.right);
}
}
return 0;
}
}
发表于 2017-05-22 19:39:02
回复(17)
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)
return run(root.right)+1;
if(root.right==null)
return run(root.left)+1;
return Math.min(run(root.left),run(root.right))+1;
}
}
编辑于 2016-05-29 21:22:53
回复(3)
【java】同样是递归和非递归2种方法，了解一下
1.先来非递归：
思路：BFS标准解法，使用next和count来记录下一层和当前层还剩下的节点数，当前层数layer
1.入队标准：节点不为空，
1.1提前退出条件，当前节点是叶子节点，左右节点都是null,返回layer
1.2left或right不为空，入队一次下一层个数(next)+1
2.出队标准：无，出队一次，当前层(count--)减一
3.更新层数：当前层剩余个 count==0时
count = next; //获取下一层个数
layer++;//遍历下一层，层数加1
next= 0;//复位
1.入队标准：节点不为空，
1.1提前退出条件，当前节点是叶子节点，左右节点都是null,返回layer
1.2left或right不为空，入队一次下一层个数(next)+1
2.出队标准：无，出队一次，当前层(count--)减一
3.更新层数：当前层剩余个 count==0时
count = next; //获取下一层个数
layer++;//遍历下一层，层数加1
next= 0;//复位
public int run(TreeNode root) {
if(root == null) return 0;
Queue<TreeNode> q = new LinkedList<>();
int next = 0;//下一层个数
int count = 1;//当前剩余个数
int layer = 1;//当前层数
q.offer(root);
while(!q.isEmpty()) {
TreeNode cur = q.poll();
--count;//每弹出一个数，当前层减一
if(cur.left == null && cur.right == null) return layer;
if(cur.left != null) {
q.offer(cur.left);
++next;//每加入一个数，当前层+1
}
if(cur.right != null) {
q.offer(cur.right);
++next;
}
if(count == 0) {//当前层剩余个数结束时，说明已经遍历结束，进入下一层
count = next;//获取下一层个数
next = 0;//复位
++layer; //遍历下一层，层数加1
}
}
return layer;
}
2.递归版本 递归：
1.出口：
0：root==null
2.递:left = run(root.left) //遍历左子树
right = run(root.right)//遍历右子树
3.归：
return left + right + 1 : 左节点或者右节点为null，就不需要比较大小
min(left,right) + 1 : 最小的深度 + 当前的深度
1.出口：
0：root==null
2.递:left = run(root.left) //遍历左子树
right = run(root.right)//遍历右子树
3.归：
return left + right + 1 : 左节点或者右节点为null，就不需要比较大小
min(left,right) + 1 : 最小的深度 + 当前的深度
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 + 1;
return Math.min(left, right) + 1;
}
编辑于 2018-06-21 08:39:06
回复(3)
class Solution {
public:
int run(TreeNode *root) {
int ldeep;
int rdeep;
if(root==NULL)
return 0;
ldeep=run(root->left);
rdeep=run(root->right);
if (ldeep==NULL)
return rdeep+1;
if (rdeep==NULL)
return ldeep+1;
if(ldeep<rdeep)
return ldeep+1;
else
return rdeep+1;
}
};
本题要注意最小深度与最大深度的区别：对于最大深度，不需要考虑当前子树是否为单子树（即一侧子树深度为0）的情况，即最大深度一直等于左右子树的最大值；对于最小深度，需要考虑当前子树是否为单子树的情况，对于双子树，其最小深度为左右子树的最小值，对于单子树，其最小深度为左右深度的最大值（因为有一侧的子树为0）。
发表于 2016-11-14 21:40:18
回复(2)
C++ solution
class Solution {
public:
int run(TreeNode *root) {
if (root == NULL) { return 0; }
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;
} else { return 1; }
}
};
发表于 2017-10-31 14:58:54
回复(7)
可以使用深度遍历，加上剪枝。一个类静态变量保存当前搜索到的最小深度，当访问到的节点深度超过这个值时剪枝，不再继续遍历，可以一定程度上改善深度优先搜索的性能。当然特殊的二叉树格式可能会导致跟不剪枝一样的结果。
class Solution {
public:
static int depth;
int run(TreeNode *root)
{
depth=1;
if(root==NULL)
return 0;
if(root->left!=NULL)
dfs(root->left, 1);
if(root->right!=NULL)
dfs(root->right, 1);
return depth;
}
void dfs(TreeNode *r, int d)
{
d++;
if(d>depth&&depth>1)
return;
if(r->left==NULL&&r->right==NULL&&(depth==1||d<depth))
{
depth=d;
return;
}
if(r->left!=NULL)
dfs(r->left, d);
if(r->right!=NULL)
dfs(r->right, d);
return;
}
};
int Solution::depth=1;
发表于 2017-08-08 16:26:07
回复(0)
//层次遍历 获取第一个叶子节点
public int run(TreeNode root) {
if(root==null)
return 0;
LinkedList<TreeNode> queue = new LinkedList<>();
int level=1;
TreeNode last,now;
last=now=root;
queue.add(root);
while(queue.size()!=0){
TreeNode node=queue.poll();
if(node.left!=null) queue.add(node.left);
if(node.right!=null) queue.add(node.right);
if(node.left==null&&node.right==null)
return level;
if(node==last){
level++;
last=queue.getLast();
}
}
return level;
}
发表于 2017-11-15 21:19:14
回复(0)
三行代码搞定
public int run(TreeNode root) {
if (root == null) return 0;
int r = run(root.right), l = run(root.left);
return r * l == 0 ? r + l + 1 : Math.min(r, l) + 1;
}
编辑于 2017-10-11 16:47:55
回复(0)
采用层次遍历，如果该层有叶节点，那么最短depth到此为止，如果没有，就遍历下一层
if (root == null) //是0
return 0;
//根不空，放入
List<TreeNode> list = new ArrayList<>();
list.add(root);
int depth = 1; //根存在，设为1
int cur = 0, last = 1; //cur开始指向当前层第一个节点,last指向下一层第一个
while (cur < list.size()){
last = list.size(); //last指向下一层第一个
//访问当前层,看一看有没有叶子节点,如果有，那么最短路径就已经求出，否则路径长度加1，指向下一层
while (cur < last){
TreeNode curNode = list.get(cur); //取当前节点
if (curNode.left == null && curNode.right == null)
return depth;
else {
if (curNode.left != null)
list.add(curNode.left);
if (curNode.right != null)
list.add(curNode.right);
}
cur++; //cur指向下一个节点
}
//当前层没有叶子节点，depth + 1
depth++;
}
return depth;
编辑于 2017-04-05 18:32:41
回复(3)
递归遍历左子树和右子树，返回最小的那个，然后加一 即为树的最小深度
class Solution {
public:
int run(TreeNode *root) {
if(root == NULL)
return 0;
int lmin = run(root->left);
int rmin = run(root->right);
if(lmin==0 && rmin == 0)
return 1;
if(lmin == 0)
lmin = INT_MAX;
if(rmin == 0)
rmin = INT_MAX;
return min(lmin, rmin)+1;
}
};
发表于 2016-03-09 12:32:13
回复(4)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型
*/
public int run (TreeNode root) {
if(root == null) {
return 0;
}
if(root.left != null && root.right != null) {
return Math.min(run(root.left), run(root.right)) + 1;
}else if(root.left != null) {
return run(root.left) + 1;
}else if(root.right != null) {
return run(root.right) + 1;
}else {
// 该节点为叶子节点
return 1;
}
}
}
发表于 2020-11-28 00:19:11
回复(0)
class Solution {
public:
/**
*
* @param root TreeNode类
* @return int整型
*/
int run(TreeNode* root) {
// write code here
if(root == nullptr) return 0;
int l = run(root->left);
int r = run(root->right);
return 1 + (l&&r ? min(l,r) : l^r);
}
};
发表于 2020-07-06 22:44:43
回复(1)
第一种使用递归思想：
public class Solution {
public int run(TreeNode root) {if(root == null) return 0;
if(root.left == null){
return 1 + run(root.right);
}
if(root.right == null){
return 1 + run(root.left);
}
return 1 + Math.min(run(root.right),run(root.left));
}
}
第二种使用层序遍历思想：
import java.util.*;
public class Solution {
public int run(TreeNode root) {
if(root==null) return 0;
if(root.left==null && root.right==null)
return 1;
LinkedList<TreeNode> queue=new LinkedList<>();
queue.add(root);
int count=0;
while(!queue.isEmpty()){
int len=queue.size();
count++;
for(int i=0; i<len; i++){
TreeNode temp=queue.remove(0);
if(temp.left==null&&temp.right==null)
return count;
if(temp.left!=null)
queue.add(temp.left);
if(temp.right!=null)
queue.add(temp.right);
}
}
return count;
}
}
public class Solution {
public int run(TreeNode root) {
if(root==null) return 0;
if(root.left==null && root.right==null)
return 1;
LinkedList<TreeNode> queue=new LinkedList<>();
queue.add(root);
int count=0;
while(!queue.isEmpty()){
int len=queue.size();
count++;
for(int i=0; i<len; i++){
TreeNode temp=queue.remove(0);
if(temp.left==null&&temp.right==null)
return count;
if(temp.left!=null)
queue.add(temp.left);
if(temp.right!=null)
queue.add(temp.right);
}
}
return count;
}
}
编辑于 2019-03-07 22:20:32
回复(0)
纪念一下：从今后，我要好好刷题，再也不浪了
import java.util.*;
public class Solution {
public int run(TreeNode root) {
if(root==null) return 0;
if(root.left==null && root.right==null)
return 1;
LinkedList<TreeNode> queue=new LinkedList<>();
queue.add(root);
int count=0;
while(!queue.isEmpty()){
int len=queue.size();
count++;
for(int i=0; i<len; i++){
TreeNode temp=queue.remove(0);
if(temp.left==null&&temp.right==null)
return count;
if(temp.left!=null)
queue.add(temp.left);
if(temp.right!=null)
queue.add(temp.right);
}
}
return count;
}
}
编辑于 2018-07-28 19:12:00
回复(0)
没错，就是找一个叶子结点
import java.util.LinkedList;
public class Solution {
public int run(TreeNode root) {
if (root == null){
return 0;
}
if (root.left==null && root.right==null){
return 1;
}
LinkedList<TreeNode> list = new LinkedList<TreeNode>();
list.addLast(root);
list.addLast(null);
int deepth = 1;
while (!list.isEmpty()){
TreeNode treeNode = list.pop();
if (treeNode == null){
list.addLast(null);
deepth++;
continue;
}
if (treeNode.left==null && treeNode.right==null){
return deepth;
}
if (treeNode.left != null){
list.addLast(treeNode.left);
}
if (treeNode.right != null){
list.addLast(treeNode.right);
}
}
return deepth;
}
}
发表于 2017-09-06 21:51:52
回复(0)
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)
问题信息
难度：
471条回答
1574收藏
67671浏览
通过挑战的用户
查看代码-
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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
