首页 > 编程语言 >BFS场景样例测试--最短路径--用Java实现

BFS场景样例测试--最短路径--用Java实现

时间:2022-12-25 21:44:56浏览次数:43  
标签:TreeNode cur -- 样例 int step new Java left

我们今天研究下最短路径 用BFS来实现

 

首先确定数据结构

/**
 * 二叉树数据结构节点
 */
public class TreeNode {

    int value;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val){
        this.value = val;
    }
}

然后走下场景的代码

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class BFSDemoTwo {
    /***
     * 找出起点到终点最短距离 
     * @param start
     * @return
     */
    public int distanceOrder(TreeNode start,TreeNode target){

        Queue<TreeNode> q = new ArrayDeque<>();

        // 将开始节点加入队列
        if(null != start){
            q.offer(start);
        }


        int step = 0;

        while (!q.isEmpty()){
            int sz = q.size();

            // TODO  这里有优化空间 暂时不修改
            List<Integer> num = new ArrayList<>();

            for (int i = 0; i < sz; i++) {
                TreeNode cur = q.poll();

                if(cur.value == target.value){
                    return step;
                }

                // 将左右节点加入队列 以备下一轮迭代
                if(cur.left!=null){
                    q.offer(cur.left);
                }

                if(cur.right!=null){
                    q.offer(cur.right);
                }

                num.add(cur.value);

            }
            step++;

        }
        return step;
    }

    public static void main(String[] args){

        // 构建测试数据

        TreeNode root = new TreeNode(9);
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node7 = new TreeNode(7);
        TreeNode node5 = new TreeNode(5);
        TreeNode node4 = new TreeNode(4);

        root.left = node1;
        root.right = node2;
        node2.left = node7;
        node2.right = node5;
        node7.left = node4;

        BFSDemoTwo bfsDemoTwo = new BFSDemoTwo();

        int step = bfsDemoTwo.distanceOrder(root,node4);
        System.out.println("步数是:"+step);

    }
}

 

运行结果

 

 

标签:TreeNode,cur,--,样例,int,step,new,Java,left
From: https://www.cnblogs.com/zhou-789profession/p/17004644.html

相关文章

  • Django之forms组件内容,Django中间件
    目录Django之forms组件内容,Django中间件今日内容概要今日内容详细forms组件渲染标签forms组件展示信息forms组件校验补充forms组件参数补充forms组件源码剖析modelform组件......
  • 软件工程复习捏
    第一章软件工程软件危机软件危机是指落后的软件生产方式无法满足迅速增长的计算机软件需求,从而导致软件开发与维护过程中出现一系列严重问题的现象。原因:1软件规模越......
  • Java编程思想13
    第十八章:JavaI/O系统对程序语言的设计者而言,创建一个好的输入/输出(I/O)系统是一项艰难的任务。File类既能代表一个特定文件的名称,又能代表一个目录下一组文件的名称。下......
  • 线程私有数据
    所谓线程私有数据是除局部数据和全局数据的第三类数据,这个概念是随着线程的诞生而提出来的。假设你的一个线程里面嵌套调用了很多函数,而你又需要在这些函数之间使用一个公......
  • 20221321杨渝第八次试验
    实验配置实验相关知识背景LAMP是指一组通常一起使用来运行动态网站或者服务器的自由软件名称首字母缩写:Linux,操作系统,openEuler就是一种Linux发行版Apache,Web服务器......
  • 实验5
    实验任务3#include<stdio.h>#include<string.h>#defineN100typedefstruct{charnum[10];//学号ints1;//期末成绩int......
  • 匡园深学系统食用方法3.0
    前言Before又双叒叕要开始上网课了倒闭的博客又开张了可惜中育课堂助手加入了设备码识别不能快乐地截图了于是,我们把目光转向了中育飞车助手配置要求Requirement......
  • 如何用webgl(three.js)搭建一个3D库房,3D仓库3D码头,3D集装箱,车辆定位,叉车定位可视
    使用three.js(webgl)搭建智慧楼宇、3D园区、3D厂房、3D码头、3D海关、3D仓库、3D定位、三维室内定位、设备检测、数字孪生、物联网3D、物业3D监控、物业......
  • 微信公众号下载视频
    如图,将视频下载到本地步骤用电脑浏览器打开网页链接,按【F12】-点击【网络】按F5刷新一下网页,再重新播放视频,按照文件大小从高到低排序双击左边第一个内容,右击url复制值将复......
  • TCP/IP概述
    7.1.1TCP/IP的分层模型7.1.2TCP/IP的分层模型特点7.1.3TCP/IP核心协议  OSI协议参考模型,它是基于国际标准化组织(ISO)的建议发展起来的,它分为7个层次:应用层、表示层......