二叉樹廣度優先搜尋(BFS)算法 Java

在二叉樹中，廣度優先搜尋又可以稱為層序周遊

上圖中的二叉樹經過層序周遊後的結果就是1、2、3、4、5

那我們該如何去一層一層地去儲存二叉樹的節點，很明顯，隻依賴二叉樹的結構本身是無法去層序儲存二叉樹中的節點的，是以我們就需要借助隊列來幫我們去儲存每一層裡面周遊過的元素。

實作原理

1、先将根節點1入隊列

2、将1出隊列，然後将節點1的左右子節點2和3加入隊列

3、将節點2和3出隊列，将其左右子節點放入隊列

4、最後全部出隊列。

例題講解：

以牛客劍指Offer中的題NC297為例，題目要求如下

代碼如下：

import java.util.*;
/**
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> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }        

        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);

        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            list.add(node.val);
            if(node.left != null){
                queue.add(node.left);
            }
            if(node.right != null){
                queue.add(node.right);
            }
        }
        return list;
    }
}