about BFS
Wed, Sep 1, 2021
17-minute read
master BFS in algo
- Binary Tree ZigZag Level Order Traversal 103
- Populating Next Right Pointers in Each Node 116
- Populating Next Right Pointers in Each Node II 117
- Binary Tree Right Side View 199
- Number of Islands 200
- Minesweeper 529
- All Nodes Distance K in Binary Tree 863
- Shortest Path in a Grid with Obstacles Eliminat
- Maximum Candies You Can Get from Boxes 1298
Binary Tree ZigZag Level Order Traversal 103
这道题我经常脑子犯糊涂，第一个解法是完全按 BFS 套路来，然后偶数层 list 反转 Collections.reverse
BFS 经典，从 q 后面进
- 1 1
- 2 3 2
- 345 3
- 4567
第二个是反转加入到 list 头上, 跟上面的用自带的 reverse 是一个思路，这里是手动加到头上，用 Linked list 更好
- 1 1 sub: 1
- 2 3 2 sub 3 2
- 345 3
- 4567
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> q = new ArrayDeque<>();
q.offer(root);
boolean zigzag = false;
while (!q.isEmpty()) {
List<Integer> list = new LinkedList<>();
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode cur = q.poll();
if (zigzag) {
list.add(0 , cur.val);
} else {
list.add(cur.val);
}
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
}
res.add(list);
zigzag = !zigzag;
}
return res;
}
On Runtime: 1 ms, faster than 86.05% of Java online submissions for Binary Tree Zigzag Level Order Traversal. Memory Usage: 40.8 MB, less than 91.73% of Java online submissions for Binary Tree Zigzag Level Order Traversal.
第三个是 deque
- 1 1 从头 poll
- 2 3 从背后塞 从背后 poll 3
- 542 从背后塞 从背后 poll 2
- 7654 从头 poll
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root==null)
return result;
boolean level=true;
Deque<TreeNode> deque=new ArrayDeque<>();
deque.offer(root);
while (!deque.isEmpty())
{
List<Integer> sublist = new ArrayList<Integer>();
if (level)
{
int count=deque.size();
for (int i = 0; i < count; i++)
{
TreeNode cur = deque.pollFirst();
sublist.add(cur.val);
if (cur.left != null)
deque.offerLast(cur.left);
if (cur.right != null)
deque.offerLast(cur.right);
}
}
else
{
int count=deque.size();
for (int i = 0; i < count; i++)
{
TreeNode cur = deque.pollLast();
sublist.add(cur.val);
if (cur.right != null)
deque.offerFirst(cur.right);
if (cur.left != null)
deque.offerFirst(cur.left);
}
}
level=!level;
result.add(sublist);
}
return result;
从前面的大部分对树的操作来看，都需要从根节点到下一层一层的查找。
一颗满树，每层节点数大概为 2n-1，那么最底层的节点个数比树的其它节点数多 1，因此，查找、插入或删除节点的操作大约有一半都需要找到底层的节点，另外四分之一的节点在倒数第二层，依次类推。
总共 N 层共有 2n-1 个节点，那么时间复杂度为 O(logn),底数为 2。
在有 1000000 个数据项的无序数组和链表中，查找数据项平均会比较 500000 次，但是在有 1000000 个节点的二叉树中，只需要 20 次或更少的比较即可。
有序数组可以很快的找到数据项，但是插入数据项的平均需要移动 500000 次数据项，在 1000000 个节点的二叉树中插入数据项需要 20 次或更少比较，在加上很短的时间来连接数据项。
同样，从 1000000 个数据项的数组中删除一个数据项平均需要移动 500000 个数据项，而在 1000000 个节点的二叉树中删除节点只需要 20 次或更少的次数来找到他，然后在花一点时间来找到它的后继节点，一点时间来断开节点以及连接后继节点。
所以，树对所有常用数据结构的操作都有很高的效率。
遍历可能不如其他操作快，但是在大型数据库中，遍历是很少使用的操作，它更常用于程序中的辅助算法来解析算术或其它表达式。
Populating Next Right Pointers in Each Node 116
You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.
层序遍历，因为需要用 root 来定 next 所以用 preorder
由于是完全二叉树，所以若节点的左子结点存在的话，其右子节点必定存在
Time Complexity : O(n), where n is the number of elements in root
Space Complexity : O(log n), for recursion stack of a perfect BST
public Node connect(Node root) {
if (root == null || root.left == null) {
return root;
}
root.left.next = root.right;
// 2.next 有 3，
if (root.next != null) {
root.right.next = root.next.left;
}
connect(root.left);
connect(root.right);
return root;
}
public Node connect1(Node root) {
if(root == null)
return root;
conn(root.left, root.right);
return root;
}
private void conn(Node left, Node right) {
if(left == null)
return;
left.next = right;
conn(left.left, left. right);
conn(left.right, right.left);
conn(right.left, right.right);
}
using a queue
On, time and space
public Node connect(Node root) {
if (root == null) {
return root;
}
Queue<Node> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
Node prev = null;
for (int i = 0; i < size; i++) {
Node cur = q.poll();
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
if (prev != null) {
prev.next = cur;
}
prev = cur;
}
}
return root;
}
Time Complexity : O(n), where n is the number of elements in root
Space Complexity : O(1)
public Node connect2(Node root) {
if(root == null)
return root;
Node level = root;
while(level.left != null) {
Node curr = level;
while(curr != null) {
curr.left.next = curr.right;
if(curr.next != null)
curr.right.next = curr.next.left;
curr = curr.next;
}
level = level.left;
}
return root;
}
Populating Next Right Pointers in Each Node II 117
Given a binary tree
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.
非完全二叉树， 题目要求 constant space
public Node connect(Node root) {
if (root == null) {
return root;
}
Queue<Node> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
Node prev = null;
for (int i = 0; i < size; i++) {
Node cur = q.poll();
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
// prev == null , cur is the first node
if (prev != null) {
prev.next = cur;
}
prev = cur;
}
}
return root;
}
不需要用 queue， 把每一行都看作一个链表
. 6
/
2 8
/ /
0 7 9
cur 2
pre = dummy(-1)
step 1:
prev.next = cur.left;
prev = prev.next;
dummy(-1) -> prev(0)
step2:
cur = 8;
prev.next = cur.left;
prev = prev.next;
dummy(-1) -> 0 -> prev(7)
step3:
cur = 8;
prev.next = cur.right;
prev = prev.next;
dummy(-1) -> 0 -> 7 -> prev(9)
public Node connect(Node root) {
if(root == null) {
return root;
}
// cur 每一层链表的父层
Node cur = root;
while(cur != null) {
// 每一层都设一个 dummy 头
Node dummy = new Node(-1);
Node prev = dummy;
// prev 是这层的访问节点
while (cur != null) {
if (cur.left != null) {
prev.next = cur.left;
prev = prev.next;
}
if (cur.right != null) {
prev.next = cur.right;
prev = prev.next;
}
// 父层的下一个节点
cur = cur.next;
}
// 当前层遍历好后，赋值给 cur， 等于cur 下降到了这一层，开始新得遍历
cur = dummy.next;
}
return root;
}
Binary Tree Right Side View 199
这题 recursion 我有个误区，就是我第一反应就是只往右边就可以了，但实际上这只是最右边，也包括 root.right.right == null, root.right.left != null, 然后 再往下的右孩子是有值的这种情况
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example 1:
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
用 queue 入队出队，空间复杂度 O(n), 额外的队列空间
打印时候： if (i == size - 1) res.add(node.val); 将当前层的最后一个节点放入结果
DFS
根节点 -》 右子树 -》 左子树， 保证每层最先访问的是最右边的节点
public List<Integer> rightSideView(TreeNode root) {
List<Integer> list = new ArrayList<>();
return helper(root, list, 0);
}
List<Integer> helper(TreeNode root, List<Integer> list, int level) {
if (root == null) {
return list;
}
// 0 1, 1
if (list.size() == level) {
list.add(root.val);
}
helper(root.right, list, level + 1);
helper(root.left, list, level + 1);
return list;
}
if (list.size() == level) list.add(root.val); 当前节点所在的层还没有出现在 res 里， 说明这是第一个被访问的节点
Number of Islands 200
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
BFS: 用 queue， 判断队列首部节点是否未越界且为 1 ， 1 的话置零，然后把节点的上下左右都加入队列
public int numIslands(char[][] grid) {
int count = 0;
boolean[][] visited = new boolean[grid.length][grid[0].length];
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (!visited[i][j] && grid[i][j] == '1') {
bfs(grid, i, j, visited);
count++;
}
}
}
return count;
}
private void bfs(char[][] grid, int i, int j, boolean[][] visited) {
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[] {i, j});
while (!q.isEmpty()) {
int[] cur = q.poll();
i = cur[0]; j = cur[1];
if (0 <= i && i < grid.length && 0 <= j && j < grid[0].length && grid[i][j] == '1') {
visited[i][j] = true;
grid[i][j] = '0';
q.offer(new int[]{i + 1, j});
q.offer(new int[]{i - 1, j});
q.offer(new int[]{i , j + 1});
q.offer(new int[]{i , j - 1});
}
}
}
如何是 dfs 也是类似的，
二叉树
void traverse(TreeNode root) {
if (root == null) {
return;
}
traverse(root.left);
traverse(root.right);
}
图的套路
void traverse(int[][] grid, int r, int c) {
if (!inArea(grid, r, c)) {
return;
}
traverse(grid, r - 1, c);
traverse(grid, r + 1, c);
traverse(grid, r, c - 1);
traverse(grid, r, c + 1);
// 判断坐标 r ，c 是否在网格里
boolean inArea(int[][] grid, int r, int c) {
return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;
}
}
避免重复遍历
void traverse(int[][] grid, int r, int c) {
if (!inArea(grid, r, c)) {
return;
}
// 不是岛屿
if (grid[r][c] != 1) {
return;
}
grid[r][c] = 2; // 已遍历过
traverse(grid, r - 1, c);
traverse(grid, r + 1, c);
traverse(grid, r, c - 1);
traverse(grid, r, c + 1);
// 判断坐标 r ，c 是否在网格里
boolean inArea(int[][] grid, int r, int c) {
return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;
}
}
public int numIslands(char[][] grid) {
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
dfs(grid, i, j);
count++;
}
}
}
return count;
}
private void dfs(char[][] grid, int i, int j) {
if (0 > i || i >= grid.length || 0 > j || j >= grid[0].length || grid[i][j] == '0') {
return;
}
grid[i][j] = '0';
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i , j+ 1);
dfs(grid, i , j- 1);
}
Minesweeper 529
Let's play the minesweeper game (Wikipedia, online game)!
You are given an m x n char matrix board representing the game board where:
'M' represents an unrevealed mine,
'E' represents an unrevealed empty square,
'B' represents a revealed blank square that has no adjacent mines (i.e., above, below, left, right, and all 4 diagonals),
digit ('1' to '8') represents how many mines are adjacent to this revealed square, and
'X' represents a revealed mine.
You are also given an integer array click where click = [clickr, clickc] represents the next click position among all the unrevealed squares ('M' or 'E').
Return the board after revealing this position according to the following rules:
If a mine 'M' is revealed, then the game is over. You should change it to 'X'.
If an empty square 'E' with no adjacent mines is revealed, then change it to a revealed blank 'B' and all of its adjacent unrevealed squares should be revealed recursively.
If an empty square 'E' with at least one adjacent mine is revealed, then change it to a digit ('1' to '8') representing the number of adjacent mines.
Return the board when no more squares will be revealed.
Example 1:
Input: board = [["E","E","E","E","E"],["E","E","M","E","E"],["E","E","E","E","E"],["E","E","E","E","E"]], click = [3,0]
Output: [["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]
这里是 8 个方向
int[] dx = {-1, 1, 0, 0, -1, 1, -1, 1};
int[] dy = { 0, 0, -1, 1,-1, 1, 1, -1};
public char[][] updateBoard(char[][] board, int[] click) {
// if the first step is the M
int x = click[0], y = click[1];
if (board[x][y] == 'M'){
board[x][y] == 'X';
return board;
}
// if the first step is E, bfs to the 8 dir
int m = board.length, n = board[0].length;
boolean[][] visited = new boolean[m][n];
visited[x][y] = true;
Queue<int[]> q = new ArrayDeque<>();
q.offer(new int[]{x, y});
while (!q.isEmpty()) {
int[] cur = q.poll();
int i = cur[0], j = cur[1];
// 判断周围是否有雷
int count = 0;
for (int k = 0; k < 8; k++) {
int newX = i + dx[k];
int newX = i + dx[k];
if (newX >= 0 && newX < board.length && newY >= 0 && newY < board[0].length && board[newX][newY] == 'M' ) {
count++;
}
}
// if (i, j) 有雷，该位置为 x， 否则就是 B, 没点到所以这里的 M 不用变成 X
if (count > 0) {
board[i][j] = (char)(count + '0');
} else {
board[i][j] = 'B';
for (int k = 0; k < 8; k++) {
int newX = i + dx[k];
int newY = j + dy[k];
if (newX < 0 || newX >= board.length || newY < 0 || newY >= board[0].length || board[newX][newY] != 'E' || visited[newX][newY]) {
continue;
}
visited[newX][newY] = true;
q.offer(new int[]{newX, newY});
}
}
}
return board;
}
}
}
[
["E","E","E","E","E","E","E","E"],
["E","E","E","E","E","E","E","M"],
["E","E","M","E","E","E","E","E"],
["M","E","E","E","E","E","E","E"],
["E","E","E","E","E","E","E","E"],
["E","E","E","E","E","E","E","E"],
["E","E","E","E","E","E","E","E"],
["E","E","M","M","E","E","E","E"] ]
[0,0]
dfs
- 起点是 M， 修改好，游戏结束
- 空，E， 向 8 方向搜索，直到遇到雷区域停止
int[] dx = {-1, 1, 0, 0, -1, 1, -1, 1};
int[] dy = { 0, 0, -1, 1,-1, 1, 1, -1};
public char[][] updateBoard(char[][] board, int[] click) {
int x = click[0], y = click[1];
if (board[x][y] == 'M'){
board[x][y] = 'X';
}else { // 向周围开始 8 领域进行搜索
dfs(board, x, y);
}
return board;
}
private void dfs(char[][] board, int i, int j) {
// 判断周围是否有雷
int count = 0;
for (int k = 0; k < 8; k++) {
int newX = i + dx[k];
int newY = j + dy[k];
if (newX >= 0 && newX < board.length && newY >= 0 && newY < board[0].length && board[newX][newY] == 'M' ) {
count++;
}
}
// if (i, j) 有雷，该位置为 x， 否则就是 B, 没点到所以这里的 M 不用变成 X
if (count > 0) {
board[i][j] = (char)(count + '0');
return;
}
// 如果没有雷，该位置改为 B， 向 8 领域的空地继续搜索
board[i][j] = 'B';
for (int k = 0; k < 8; k++) {
int newX = i + dx[k];
int newY = j + dy[k];
if (newX < 0 || newX >= board.length || newY < 0 || newY >= board[0].length || board[newX][newY] != 'E') {
continue;
}
dfs(board, newX, newY);
}
}
All Nodes Distance K in Binary Tree 863
Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node.
You can return the answer in any order.
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]
Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.
hashmap, find the target, dfs
我的思路是 bfs 找到 target， 然后 dfs 距离
但是没想到的思路是直接 dfs，储存 distance, 返回 distance， 然后 dfs 更快
time On
Map<TreeNode, Integer> map = new HashMap();
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
// find the target,
find(root, target);
// bfs
dfs(root, target, k, map.get(root), res);
return res;
}
private int find(TreeNode root, TreeNode target) {
if (root == null) {
return -1;
}
if (root == target) {
map.put(root, 0);
return 0;
}
int left = find(root.left, target);
if (left >= 0) {
map.put(root, left + 1);
return left + 1;
}
int right = find(root.right, target);
if (right >= 0) {
map.put(root, right + 1);
return right + 1;
}
return -1;
}
// dfs
private void dfs(TreeNode root, TreeNode target, int k, int length, List<Integer> res) {
if (root == null) {
return ;
}
if (map.containsKey(root)) {
length = map.get(root);
}
if (length == k) {
res.add(root.val);
}
dfs(root.left, target, k, length+ 1, res);
dfs(root.right, target, k, length+ 1, res);
}
空间复杂度：O(n)
由于输入的二叉树没有记录父结点，为此，我们从根结点 \textit{root}root 出发，使用深度优先搜索遍历整棵树，同时用一个哈希表记录每个结点的父结点。
然后从 \textit{target}target 出发，使用深度优先搜索遍历整棵树，除了搜索左右儿子外，还可以顺着父结点向上搜索。
代码实现时，由于每个结点值都是唯一的，哈希表的键可以用结点值代替。此外，为避免在深度优先搜索时重复访问结点，递归时额外传入来源结点 \textit{from}from，在递归前比较目标结点是否与来源结点相同，不同的情况下才进行递归。
Map<TreeNode, Integer> map = new HashMap();
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
List<Integer> res = new ArrayList<>();
// record the parent ,map,
find(root);
// start from target, dfs
dfs(target, null, 0, k, res);
return res;
}
private void find(TreeNode root) {
if (root.left != null) {
map.put(root.left.val, root);
find(root.left);
}
if (root.right != null) {
map.put(root.right.val, root);
find(root.right);
}
}
// dfs
private void dfs(TreeNode node, TreeNode from, int depth, int k, List<Integer> res) {
if (root == null) {
return ;
}
if (depth == k) {
res.add(root.val);
return;
}
if (node.left != from) {
dfs(node.left, node, depth + 1, k, res);
}
if (node.right != from) {
dfs(node.right, node, depth + 1, k, res);
}
if (map.get(node.val) != from) {
dfs(map.get(node.val), node, depth + 1, k, res);
}
}
Shortest Path in a Grid with Obstacles Elimina
You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step.
Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.
Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
Output: 6
Explanation:
The shortest path without eliminating any obstacle is 10.
The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).
PriorityQueue
int[][] dirs = new int[][]{{0, 1},{0, -1},{1, 0},{-1, 0} };
public int shortestPath(int[][] grid, int k) {
int m = grid.length, n = grid[0].length;
//
int[][] visited = new int[m][n];
for (int i = 0; i < m; i++) {
Arrays.fill(visited[i], -1);
}
PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[3] - b[3]);
if (grid[0][0] == 1) {
k--;
}
q.offer(new int[]{0, 0, k, 0});
visited[0][0] = k;
while (!q.isEmpty()) {
int[] cur = q.poll();
int r = cur[0], c = cur[1], ob = cur[2];
int step = cur[3];
if (r == m - 1 && c == n - 1) {
return step;
}
for (int[] dir : dirs) {
int nR = dir[0] + r;
int nC = dir[1] + c;
if (nR >= 0 && nR < m && nC >= 0 && nC < n) {
int nob = ob - grid[nR][nC];
if (nob >= 0 && nob > visited[nR][nC]) {
q.offer(new int[]{nR, nC, nob, step + 1});
visited[nR][nC] = nob;
}
}
}
}
return -1;
}
Maximum Candies You Can Get from Boxes 1298
You have n boxes labeled from 0 to n - 1. You are given four arrays: status, candies, keys, and containedBoxes where:
status[i] is 1 if the ith box is open and 0 if the ith box is closed,
candies[i] is the number of candies in the ith box,
keys[i] is a list of the labels of the boxes you can open after opening the ith box.
containedBoxes[i] is a list of the boxes you found inside the ith box.
You are given an integer array initialBoxes that contains the labels of the boxes you initially have. You can take all the candies in any open box and you can use the keys in it to open new boxes and you also can use the boxes you find in it.
Return the maximum number of candies you can get following the rules above.
Example 1:
Input: status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0]
Output: 16
Explanation: You will be initially given box 0. You will find 7 candies in it and boxes 1 and 2.
Box 1 is closed and you do not have a key for it so you will open box 2. You will find 4 candies and a key to box 1 in box 2.
In box 1, you will find 5 candies and box 3 but you will not find a key to box 3 so box 3 will remain closed.
Total number of candies collected = 7 + 4 + 5 = 16 candy.
public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
// status = [1,0,0,0,0,0]
int n = status.length; // count of boxes
boolean[] opened = new boolean[n];
boolean[] toBeOpened = new boolean[n];
Queue<Integer> q = new ArrayDeque<>();
// initialBoxes = [0]
for (int v : initialBoxes) {
q.offer(v);
toBeOpened[v] = true; // toBeOpened[0] = true;
}
int candy = 0;
while (!q.isEmpty()) {
int cur = q.poll();
if (status[cur] == 1 && !opened[cur]) { // 1伦 true
candy += candies[cur]; //
opened[cur] = true; //opened[0] = true
for (int k : keys[cur]) { // 1
status[k] = 1;
if (toBeOpened[k]) {
q.offer(k);
}
}
for (int k : containedBoxes[cur]) {
toBeOpened[k] = true;
q.offer(k);
}
}
}
return candy;
}
