BFS

102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

class Solution {
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return res;
        }
        bfs(Collections.singletonList(root));
        return res;
    }

    public void bfs(List<TreeNode> list) {
        if (list.isEmpty()) {
            return;
        }
        res.add(list.stream().map(it -> it.val).collect(Collectors.toList()));
        List<TreeNode> next = new ArrayList<>();
        for (TreeNode treeNode : list) {
            if (treeNode.left != null) {
                next.add(treeNode.left);
            }
            if (treeNode.right != null) {
                next.add(treeNode.right);
            }
        }
        bfs(next);
    }
}

103. 二叉树的锯齿形层序遍历

class Solution {
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) {
            return res;
        }
        bfs(Collections.singletonList(root), true);
        return res;
    }

    public void bfs(List<TreeNode> layer, Boolean left) {
        if (layer.isEmpty()) {
            return;
        }
        List<Integer> collect = layer.stream().map(it -> it.val).collect(Collectors.toList());
        if (!left) {
            Collections.reverse(collect);
        }
        res.add(collect);
        bfs(layer.stream().filter(it -> !(it.left == null && it.right == null)).flatMap(it -> Stream.of(it.left, it.right).filter(Objects::nonNull)).collect(Collectors.toList()), !left);
    }

}

图像渲染

有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。

你也被给予三个整数 sr ,  sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。

为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 newColor 。

最后返回 经过上色渲染后的图像 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/flood-fill
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};

    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int startIndex = image[sr][sc];
        if (startIndex == color) {
            return image;
        }
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{sr, sc});
        // BFS
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            for (int i = 0; i < 4; i++) {
                int curX = poll[0] + dx[i], curY = poll[1] + dy[i];
                if (curX >= 0 && curX < image.length && curY >= 0 && curY < image[0].length && image[curX][curY] == startIndex) {
                    image[curX][curY] = color;
                    queue.add(new int[]{curX, curY});
                }
            }
        }
        image[sr][sc] = color;
        return image;
    }
}