我们今天研究下最短路径 用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