廣度優(yōu)先遍歷類似于二叉樹的層次遍歷。廣度優(yōu)先搜索是從根結(jié)點(diǎn)開(kāi)始沿著樹的寬度搜索遍歷，也就是按層次的去遍歷；從上往下對(duì)每一層依次訪問(wèn)，在每一層中，從左往右（也可以從右往左）訪問(wèn)結(jié)點(diǎn)，訪問(wèn)完一層就進(jìn)入下一層，直到?jīng)]有結(jié)點(diǎn)可以訪問(wèn)為止。

廣度優(yōu)先搜索(Breadth First Search)(其實(shí)是二叉樹的層次遍歷),又叫寬度優(yōu)先搜索或橫向優(yōu)先搜索，是從根結(jié)點(diǎn)開(kāi)始沿著樹的寬度搜索遍歷。

從上往下對(duì)每一層依次訪問(wèn)，在每一層中，從左往右（也可以從右往左）訪問(wèn)結(jié)點(diǎn)，訪問(wèn)完一層就進(jìn)入下一層，直到?jīng)]有結(jié)點(diǎn)可以訪問(wèn)為止。

上面二叉樹的遍歷順序?yàn)椋篈BCDEFG. 可以利用隊(duì)列實(shí)現(xiàn)廣度優(yōu)先搜索。

廣度優(yōu)先搜索算法：

保留全部結(jié)點(diǎn)，占用空間大； 無(wú)回溯操作(即無(wú)入棧、出棧操作)，運(yùn)行速度快。

廣度優(yōu)先搜索算法，一般需存儲(chǔ)產(chǎn)生的所有結(jié)點(diǎn)，占用的存儲(chǔ)空間要比深度優(yōu)先搜索大得多，因此，程序設(shè)計(jì)中，必須考慮溢出和節(jié)省內(nèi)存空間的問(wèn)題。但廣度優(yōu)先搜索法一般無(wú)回溯操作，即入棧和出棧的操作，所以運(yùn)行速度比深度優(yōu)先搜索要快些。

示例：

其過(guò)程檢驗(yàn)來(lái)說(shuō)是對(duì)每一層節(jié)點(diǎn)依次訪問(wèn)，訪問(wèn)完一層進(jìn)入下一層，而且每個(gè)節(jié)點(diǎn)只能訪問(wèn)一次。對(duì)于上面的例子來(lái)說(shuō)，廣度優(yōu)先遍歷的 結(jié)果是：A,B,C,D,E,F,G,H,I(假設(shè)每層節(jié)點(diǎn)從左到右訪問(wèn))。

廣度優(yōu)先遍歷各個(gè)節(jié)點(diǎn)，需要使用到隊(duì)列（Queue）這種數(shù)據(jù)結(jié)構(gòu)，queue的特點(diǎn)是先進(jìn)先出，其實(shí)也可以使用雙端隊(duì)列，區(qū)別就是雙端隊(duì)列首位都可以插入和彈出節(jié)點(diǎn)。整個(gè)遍歷過(guò)程如下：

首先將A節(jié)點(diǎn)插入隊(duì)列中，queue（A）;

將A節(jié)點(diǎn)彈出，同時(shí)將A的子節(jié)點(diǎn)B，C插入隊(duì)列中，此時(shí)B在隊(duì)列首，C在隊(duì)列尾部，queue（B，C）；

將B節(jié)點(diǎn)彈出，同時(shí)將B的子節(jié)點(diǎn)D，E插入隊(duì)列中，此時(shí)C在隊(duì)列首，E在隊(duì)列尾部，queue（C，D，E）;

將C節(jié)點(diǎn)彈出，同時(shí)將C的子節(jié)點(diǎn)F，G，H插入隊(duì)列中，此時(shí)D在隊(duì)列首，H在隊(duì)列尾部，queue（D，E，F(xiàn)，G，H）；

將D節(jié)點(diǎn)彈出，D沒(méi)有子節(jié)點(diǎn)，此時(shí)E在隊(duì)列首，H在隊(duì)列尾部，queue（E，F(xiàn)，G，H）；

…依次往下，最終遍歷完成

Java代碼大概如下：

public class TreeNode {     int val = 0;     TreeNode left = null;     TreeNode right = null;      public TreeNode(int val) {         this.val = val;     } } public class Solution {     public ArrayList<Integer> wide(TreeNode root) {         ArrayList<Integer> lists=new ArrayList<Integer>();         if(root==null)             return lists;         Queue<TreeNode> queue=new LinkedList<TreeNode>();         queue.offer(root);         while(!queue.isEmpty()){             TreeNode node = queue.poll();             if(node.left!=null){                 queue.offer(node.left);             }             if(node.right!=null){                 queue.offer(node.right);             }             lists.add(node.val); 		}         return lists;     } }