二叉樹的層序遍歷
層序遍歷是繼前序、中序、后序遍歷之后的第二類遍歷方式，
一、 層序遍歷
假設二叉樹根節點(root)所在層數為1，層序遍歷就是從根節點出發，首先訪問根節點，接著從左到右的訪問第二層上的節點，接著是第三層，以此類推直到最后一個節點，
就像圖中一樣，先從根節點A開始，接著訪問第二層的B節點，從左至右，自上而下，
文章目錄
- 二叉樹的層序遍歷
- 一、 層序遍歷
- 假設二叉樹根節點(root)所在層數為1，層序遍歷就是從根節點出發，首先訪問根節點，接著從左到右的訪問第二層上的節點，接著是第三層，以此類推直到最后一個節點，
- 就像圖中一樣，先從根節點A開始，接著訪問第二層的B節點，從左至右，自上而下，
- 二、 代碼實作
- 三、 LeetCode實戰
- 3.1 解題思路
二、 代碼實作
2.1 這里我們用一個佇列來輔助實作層序遍歷，具體做法如下，
(1) 我們都知道，佇列的特點是先進先出，一開始從根節點root開始判斷，如果佇列不為空我們就把A放進佇列當中,緊接著判斷 當前佇列是否為空，不為空的話就 彈出佇列的一個元素，這里是A，我們在以一個參考top來記錄彈出來的節點并且列印A，
（2）判斷A的左數是否為空，不為空的話就把A的左入隊，在判斷A的右是否為空，不為空的話把右入隊，
（3）繼續判斷當前佇列是否為空，不為空的花彈出一個元素，此時是將B彈出，并且列印，
(4)重復以上步驟，直到遍歷完所有節點，
代碼如下
void leverOrderTraversal(TreeNode root){
//判斷根節點是否為空，為空直接回傳，
if(root==null){
return;
}
//用一個佇列來輔助操作
Queue<TreeNode> queue=new LinkedList<>();
//首先將根節點入隊
queue.offer(root);
//寫一個回圈，如果這時候的佇列不為空就定義一個top記錄彈出的元素
while (!queue.isEmpty()){
//佇列不為空，就列印當前彈出的top
TreeNode top=queue.poll();
System.out.print(top.val+" ");
//如果top的左不為空，就把左放進佇列里
if(top.left!=null){
queue.offer(top.left);
}
//如果top的右不為空，就把右放進佇列里
if(top.right!=null){
queue.offer(top.right);
}
//放完之后在判斷佇列是否為空，不為空繼續彈出第一個元素，直到遍歷完，
}
System.out.println();
}
}
好了，這就是二叉樹的層序遍歷，相信聰明的你已經掌握了，
三、 LeetCode實戰
下面我們來做一道leetcode題在鞏固練習一下，給小伙伴附上連接，
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
和我們上面講的差不多，但你仔細觀察的話會發現，leetcode這里回傳的是一個個集合，題目給的函式的回傳值也是這樣的，
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
}
}
回傳了一個List嵌套的List，這時候你可能有點懵，其實和二維陣列是差不多一個道理的，
3.1 解題思路
題目的回傳結果是List，所以我們也要自己創建一個List，層序遍歷的代碼我們已經會寫了，題目只是不再要我們列印出來而是直接回傳一個List，我們發現每一層的list，都存放了一層的二叉樹的元素，如上圖，代碼具體的步驟我寫在備注里了，
public List<List<Integer>> levelOrder(TreeNode root) {
//函式的回傳值是List，我們就創建一個ret，
List<List<Integer>> ret=new ArrayList<>();
if(root==null){
return ret;
}
//創建佇列來實作層序遍歷
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
//用size來記錄當前這一層的大小
int size=queue.size();
List<Integer> list=new ArrayList<>();
while (size!=0){
TreeNode top=queue.poll();
list.add(top.val);
if (top.left!=null){
queue.offer(top.left);
}
if(top.right!=null){
queue.offer(top.right);
}
//剛才已經彈出去一個，所以這里size要減一個
size--;
}
//把這一次List放到ret當中,因為ret是List嵌套的List，這樣ret就能存下每一層的資料
ret.add(list);
}
//遍歷完每一層，這時回傳ret；
return ret;
}
當當當當，成功通過！
最后祝大家學習順利，面試的時候剛好能問到這道高頻題，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/292491.html
標籤：其他
上一篇：淺談演算法——演算法的基本知識點
下一篇：鏈表面試-鏈表分割（常考題）