Breadth-First Search在樹狀結構上的表現就是逐層搜尋、批次處理。反過來說只要題目能表現成Tree或Matrix的批次處理，那通常就是用BFS來解題。

在實作的時候可以用Queue或遞迴，用遞迴實作的好處是可以配合題目任意添加參數。大部分的題目每一層之間的處理是無關的，用Queue模擬BFS在解題時會比較好理解跟修改，萬一每批次都需要用到前一層的結果，那就必須改用遞迴實作。

以下是用Queue實作的範例 :

public List<List<Integer>> bfs(TreeNode root) {
    List<TreeNode> queue = new ArrayList<>(); // 處理中的佇列
    queue.add(root); // 初始化處理項目
    while (!queue.isEmpty()) {
        List<TreeNode> layer = queue;
        queue = new ArrayList<>();        
        for (TreeNode node : layer) {
            ...; // 加入下一層的處理項目
        }
        List<Integer> subResult = ...; // 處理成輸出
        result.add(subResult);
    }
    return result;
}

102. Binary Tree Level Order Traversal

本提及為經典的BFS問題，只需把範例中的加入下一層的處理項目改成加入左右節點即可。

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (null == root) // 根據題意
        return result;
    List<TreeNode> queue = new ArrayList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        List<TreeNode> layer = queue;
        queue = new ArrayList<>();
        for (TreeNode node : layer) {
            if (null != node.left) // 有左節點就加到下一層處理
                queue.add(node.left);
            if (null != node.right) // 有右節點就加到下一層處理
                queue.add(node.right);
        }
        List<Integer> subResult = layer.stream() // 轉成題目的輸出格式
            .map(node -> new Integer(node.val))
            .collect(Collectors.toList());
        result.add(subResult);
    }
    return result;
}

103. Binary Tree Zigzag Level Order Traversal

鋸齒型插入則為上一題的變形，需要多加一個變數來決定插入的方向。

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (null == root) // 根據題意
        return result;
    List<TreeNode> queue = new ArrayList<>();
    queue.add(root);
    boolean reverse = false; // 記錄目前的插入方向
    while (!queue.isEmpty()) {
        List<TreeNode> layer = queue;
        queue = new ArrayList<>();
        LinkedList<Integer> subResult = new LinkedList<>();
        for (TreeNode node : layer) {
            if (reverse) // 判斷插入方向
                subResult.addFirst(node.val);
            else
                subResult.addLast(node.val);
            if (null != node.left) // 有左節點就加到下一層處理
                queue.add(node.left);
            if (null != node.right) // 有右節點就加到下一層處理
                queue.add(node.right);
        }
        result.add(subResult);
        reverse = !reverse; // 更新插入方向
    }
    return result;
}

133. Clone Graph

public Node cloneGraph(Node root) {
    if (null == root) // 根據題意
        return null;
    Map<Integer, Node> nodes = new HashMap<>(); // 記錄節點
    List<Node> queue = new ArrayList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        List<Node> layer = queue;
        queue = new ArrayList<>();
        for (Node node : layer) {
            if (nodes.containsKey(node.val))
                continue; // 沒看過的節點就加到下一層處理
            nodes.put(node.val, node);
            queue.addAll(node.neighbors);
        }
    }
    // 複製每個節點
    for (Map.Entry<Integer, Node> entry : nodes.entrySet()) {
        Node node = entry.getValue();
        node = new Node(node.val, new ArrayList<>(node.neighbors));
        nodes.put(entry.getKey(), node);
    }
    // 將每個節點的相鄰集合替換成複製的節點
    for (Node node : nodes.values()) {
        List<Node> neighbors = node.neighbors;
        for (int j = 0; j < neighbors.size(); ++j)
            neighbors.set(j, nodes.get(neighbors.get(j).val));
    }
    return nodes.get(root.val);
}

199. Binary Tree Right Side View

本題要回傳樹狀結構每一層最右邊的節點的數值，只需將之前的102. Binary Tree Level Order Traversal改成先插入右邊的節點，然後將每層第一個節點寫回輸出即可。

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (null == root) // 根據題意
        return result;
    List<TreeNode> queue = new ArrayList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        List<TreeNode> layer = queue;
        queue = new ArrayList<>();
        for (TreeNode node : layer) {
            if (null != node.right) // 有右節點就先加到下一層處理
                queue.add(node.right);
            if (null != node.left) // 有左節點就加到下一層處理
                queue.add(node.left);
        }
        result.add(layer.get(0).val); // 每層第一個節點就是最右邊的節點
    }
    return result;
}

207. Course Schedule

本題的先修課程實際上形成一個有向圖的資料結構，我們首先把有向圖表示成edges[i][j]，表示課程 i 是課程 j 的先修課，另外用一個陣列counts[i]表示要修課程 i 之前還需要多少先修課。

構造完有向圖之後再使用BFS搜尋，只有count為零(不需要先修課)的課程才能加入佇列處理，最後記下曾經進入佇列的課程數量即可。

public boolean canFinish(int numCourses, int[][] prerequisites) {

    // 構造有向圖
    List<List<Integer>> edges = new ArrayList<>();
    int[] counts = new int[numCourses];
    for (int i = 0; i < numCourses; ++i)
        edges.add(new ArrayList<Integer>());
    for (int[] prerequisite : prerequisites) {
        edges.get(prerequisite[1]).add(prerequisite[0]);
        ++counts[prerequisite[0]]; // 記錄先修課的數量
    }

    List<Integer> queue = new ArrayList<Integer>();
    for (int i = 0; i < numCourses; ++i)
        if (counts[i] == 0)
 // 沒有先修課就加到下一層處理
            queue.add(i);

    int visited = 0;
    while (!queue.isEmpty()) {
        List<Integer> layer = queue;
        queue = new ArrayList<>();
        for (Integer u : layer) {
            for (int v: edges.get(u)) {
                --counts[v]; // 更新先修課的數量
                if (counts[v] == 0) // 沒有先修課就加到下一層處理
                    queue.add(v);
            }
        }
        visited += layer.size(); // 佇列中的課程都確認可以修
    }

    return visited == numCourses; // 回傳可以修的課程數量是否與總數相等
}

210. Course Schedule II

public int[] findOrder(int numCourses, int[][] prerequisites) {
    // 構造有向圖
    List<List<Integer>> edges = new ArrayList<>();
    for (int i = 0; i < numCourses; ++i)
        edges.add(new ArrayList<Integer>());
    int[] counts = new int[numCourses];
    for (int[] prerequisite : prerequisites) {
        edges.get(prerequisite[1]).add(prerequisite[0]);
        ++counts[prerequisite[0]]; // 記錄先修課的數量
    }
    
    int[] result = new int[numCourses];
    int resultIndex = 0;
    List<Integer> queue = new ArrayList<Integer>();
    for (int i = 0; i < numCourses; ++i)
        if (counts[i] == 0) // 沒有先修課就加到下一層處理
            queue.add(i);

    while (!queue.isEmpty()) {
        List<Integer> layer = queue;
        queue = new ArrayList<>();
        for (Integer u : layer) {
            for (int v: edges.get(u)) {
                --counts[v]; // 更新先修課的數量
                if (counts[v] == 0) // 沒有先修課就加到下一層處理
                    queue.add(v);
            }
            result[resultIndex] = u; // 佇列中的課程必定按照修課順序
            ++resultIndex;           // 直接寫入結果
        }
    }
    if (resultIndex < numCourses) // 根據題意
        return new int[0];
    return result;
}