[Leetcode 111]二叉树的最短深度 BFS/DFS
2024-09-08 19:11:37
题目
给定二叉树,求最短路径包含的节点个数
https://leetcode.com/problems/minimum-depth-of-binary-tree/
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.
Note: A leaf is a node with no children.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 2
最短路径3-9,节点2个
Example 2:
Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5
思路
BFS比DFS合适
类似题:N叉树最大深度:https://www.cnblogs.com/inku/p/15642874.html
比如二叉树左边500右边1个节点
dfs先遍历完500个节点,再遍历1节点
bfs广度优先,左右俩边只要找到left和right同时为空的节点就返回
代码
DFS
public int minDepth(TreeNode root) {
if (root == null)
return 0; if (root.left == null && root.right == null)
return 1; if (root.left == null)
return minDepth(root.right) + 1;//left为空,走right if (root.right == null)
return minDepth(root.left) + 1;//right为空,走left return 1+Math.min(minDepth(root.left), minDepth(root.right));
//返回dfs后,左右中更小的,+1(root自身节点)
}
最大深度:https://www.cnblogs.com/inku/p/9854535.html
BFS
其实就是层次遍历
左右节点为空时就返回的限制,成了min
public int minDepth(TreeNode root) {
if(root==null)
return 0;
Queue<TreeNode> q=new LinkedList<>();
q.offer(root);
int ans=1;
while(!q.isEmpty()){
int size=q.size();
for(int i=0;i<size;i++) {
TreeNode cur=q.remove();
if (cur.left==null&&cur.right==null)
return ans;
if(cur.left!=null)
q.offer(cur.left);
if(cur.right!=null)
q.offer(cur.right);
}
ans++;
}
return ans;
}
最新文章
- 数据存储与IO(二)
- org.apache.ibatis.builder.IncompleteElementException: Could not find parameter map
- C# 线程--第三线程池
- RMQ问题
- Ubuntu下安装vmware 9.0 + 注册码
- Android Notification (转)
- onsite
- 读入一个自然数n,计算其各位数字之和,用汉语拼音写出和的每一位数字。 输入格式:每个测试输入包含1个测试用例,即给出自然数n的值。这里保证n小于10的100次幂。 输出格式:在一行内输出n的各位数字之和的每一位,拼音数字间有1 空格,但一行中最后一个拼音数字后没有空格。 输入样例: 1234567890987654321123456789 输出样例: yi san wu
- Mysql隔离级别,锁与MVCC
- DataReader分页性能测试
- fillder--信息面板显示请求耗时列
- cs特征性以及数据库的连接
- JS高级 - 面向对象3(面向过程改写面向对象)
- 让 Python 更加充分的使用 Sqlite3
- 金九银十跳槽季,程序员面试点解析之Java专场
- webStorm常用设置之过滤文件夹
- Python之旅:列表
- In 和Exists
- vue - nodejs
- [Python 多线程] RLock可重入锁 (九)