求二叉树的最小深度深度优先和广度优先
自己建一个二叉树,然后分别使用深度优先和广度优先找到二叉树的最小深度。
代码中有注释哦~
package Bilibili;
import java.util.LinkedList;
import java.util.Queue;
/**
* @author: Arbicoral
* @create: 2023-08-18 20:52
* @Description: 求一个二叉树的最小深度
*
* 深度优先:从叶子节点开始,将叶子节点标为 1,开始向上递归
* 广度优先:从根节点开始,将根节点深度设置为1,开始向下入队列
*/
public class BinaryTreeMinDepth {
public static void main(String[] args) {
TreeNode node7 = new TreeNode(7, null, null);
TreeNode node6 = new TreeNode(6, node7, null);
TreeNode node5 = new TreeNode(5, null, null);
TreeNode node4 = new TreeNode(4, null, null);
TreeNode node3 = new TreeNode(3, node6, null);
TreeNode node2 = new TreeNode(2, node4, node5);
TreeNode node1 = new TreeNode(1, node2, node3);
System.out.println(minDepth(node1));
System.out.println(minDepth2(node1));
}
/**
* 广度优先:从根节点开始
*/
private static int minDepth2(TreeNode root) {
if (root == null) return 0;
// 用一个队列进行维护
Queue<TreeNode> queue = new LinkedList<>();
root.deep = 1;//设置根节点的深度为1
// 当队列满的时候
// 调用 add()会抛出一个unchecked 异常;
// 调用 offer()会返回一个false
queue.offer(root);//把 根节点入队列
while (!queue.isEmpty()){
TreeNode node = queue.poll();// 从队列中取出一个元素
// 判断是否为 叶子节点,是的话可以直接 return
if (node.left==null && node.right==null){
return node.deep;
}
// 如果不是的话,分别判断左子节点和右子节点
if (node.left != null){
node.left.deep = node.deep 1;//左子节点的深度为当前节点的深度 1
queue.offer(node.left);//左子节点入队列
}
if (node.right != null){
node.right.deep = node.deep 1;//右子节点的深度为当前节点的深度 1
queue.offer(node.right);//右子节点入队列
}
}
return 0;
}
/**
* 深度优先:从叶子节点开始
*/
private static int minDepth(TreeNode root) {
if (root == null) return 0;
// 寻找叶子节点
if (root.left == null && root.right == null){
return 1;
}
int min = Integer.MAX_VALUE;// 保存每一个节点的最小
if (root.left != null){
min = Math.min(minDepth(root.left), min);//递归
}
if (root.right != null){
min = Math.min(minDepth(root.right), min);//递归
}
return min 1;//加上根节点
}
static class TreeNode{
private int val;
private TreeNode left;
private TreeNode right;
int deep;// 表示该节点的深度
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhicihkc
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
excel图片置于文字下方的方法
PHP中文网 06-27 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
微信提示登录环境异常是什么意思原因
PHP中文网 04-09 -
微信运动停用后别人还能看到步数吗
PHP中文网 07-22 -
微信人名旁边有个图标有什么用
PHP中文网 03-11