廣度優(yōu)先搜索的定義
廣度優(yōu)先搜索BFS類似于樹的層次遍歷算法。基本思想是：首先訪問頂點v，然后由v出發(fā)，依次訪問v的各個未被訪問過的頂點w1,w2,w3…wn。然后再訪問wi(wi是w1,w2,w3…wn中的一個)未被訪問過的鄰接點。以此類推，直到所有的頂點都被訪問過。BFS是一種分層查找的過程，每向前一步就訪問一批頂點。不同于深度優(yōu)先搜索那樣有回退的情況。為了實現(xiàn)算法，需要借助于一個輔助隊列并且以非遞歸的形式來實現(xiàn)。（來自網(wǎng)頁）

559. Maximum Depth of N-ary Tree

思路：對于上面這棵樹，BFS與DFS遍歷節(jié)點順序不同。
BFS： 1 3 2 4 5 6
DFS: 1. 3 5 6 2 4
代碼

107. Binary Tree Level Order Traversal II

BFS使用queue實現(xiàn)非遞歸，是有一個模板的。

public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> levelTraversal = new ArrayList<List<Integer>>();Queue<TreeNode> queue = new LinkedList<TreeNode>();if(root!=null){queue.add(root);}while(!queue.isEmpty()){int size = queue.size();//長度List<Integer> level = new ArrayList<Integer>();for(int i=0;i<size;i++){//遍歷本次元素TreeNode node = queue.poll();level.add(node.val);//做事情//添加子節(jié)點if(node.left!=null) queue.add(node.left);if(node.right!=null) queue.add(node.right);}levelTraversal.add(0,level);}return levelTraversal;}

這道題目也可以使用遞歸版，不過使用的有點勉強.

public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> levelTraversal = new ArrayList<List<Integer>>();levelMaker(root, levelTraversal, 0);return levelTraversal;}private void levelMaker(TreeNode node, List<List<Integer>> result, int level) {if (node == null) return;if (result.size() <= level) {result.add(0, new ArrayList<Integer>());}result.get(result.size() - 1 - level).add(node.val);levelMaker(node.left, result, level + 1);levelMaker(node.right, result, level + 1);}

代碼

總結(jié)

以上是生活随笔為你收集整理的Breadth-first Search(广度优先搜索)专题1的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。