BFS —— LeetCode 解題實作

// java
// LC 662 - Maximum Width of Binary Tree
// time = O(N), space = O(W)   W = max level width
// IDEA: level BFS carrying a heap index; width = last - first + 1 (nulls counted implicitly)
public int widthOfBinaryTree(TreeNode root) {
    if (root == null) return 0;
    int ans = 0;
    Queue<TreeNode> nodes = new LinkedList<>();
    Queue<Integer> idxs = new LinkedList<>();
    nodes.offer(root); idxs.offer(0);
    while (!nodes.isEmpty()) {
        int size = nodes.size(), first = 0, last = 0;
        for (int i = 0; i < size; i++) {
            TreeNode node = nodes.poll();
            int id = idxs.poll();
            if (i == 0) first = id;
            id -= first;                    // re-base the level at 0 -> no overflow
            last = id;
            if (node.left  != null) { nodes.offer(node.left);  idxs.offer(2 * id); }
            if (node.right != null) { nodes.offer(node.right); idxs.offer(2 * id + 1); }
        }
        ans = Math.max(ans, last + 1);      // last is already relative to first
    }
    return ans;
}

# python
# LC 662 - Maximum Width of Binary Tree
# time = O(N), space = O(W)
# IDEA: queue holds (node, index); re-base index per level to keep numbers small
def widthOfBinaryTree(root):
    if not root:
        return 0
    ans = 0
    q = deque([(root, 0)])
    while q:
        first = q[0][1]
        last = first
        for _ in range(len(q)):
            node, idx = q.popleft()
            idx -= first                    # normalize against this level's start
            last = idx
            if node.left:
                q.append((node.left, 2 * idx))
            if node.right:
                q.append((node.right, 2 * idx + 1))
        ans = max(ans, last + 1)
    return ans

# python
# LC 958 - Check Completeness of a Binary Tree
# time = O(N), space = O(W)
# IDEA: push nulls; after the first null pops, any real node means "not complete"
def isCompleteTree(root):
    q = deque([root])
    seen_null = False
    while q:
        node = q.popleft()
        if node is None:
            seen_null = True
        else:
            if seen_null:
                return False        # a real node after a gap -> not complete
            q.append(node.left)     # push children unconditionally, nulls included
            q.append(node.right)
    return True

// From LC 994 - RottingOranges.java V0
while (!queue.isEmpty() && freshOrange > 0) {  // NOTE: extra condition!
    int size = queue.size();
    time++;  // Increment FIRST - we're about to process a "minute" level

    for (int i = 0; i < size; i++) {
        int[] cur = queue.poll();
        // process neighbors, infect fresh oranges...
    }
}
return freshOrange == 0 ? time : -1;

// From LC 994 - RottingOranges.java V0-0-2, V0-1, V0-4
while (!queue.isEmpty()) {
    int size = queue.size();
    boolean rottedThisMinute = false;

    for (int i = 0; i < size; i++) {
        int[] cur = queue.poll();
        // process neighbors...
        if (/* infected a fresh neighbor */) {
            rottedThisMinute = true;
        }
    }

    if (rottedThisMinute) time++;  // Only count if actual infection happened
}
return freshOrange == 0 ? time : -1;

Scenario: After all oranges are infected

Layer N: Queue = [(2,1)], freshOrange = 1
  - time++ → time = 4
  - Process (2,1): infect (2,2)
  - freshOrange = 0, Queue = [(2,2)]

Layer N+1: Queue = [(2,2)], freshOrange = 0
  - WITHOUT `freshOrange > 0`: time++ → time = 5 (WRONG! over-count)
  - WITH `freshOrange > 0`: Exit loop, return time = 4 (CORRECT!)

// CORRECT: Exit early when nothing left to infect
while (!queue.isEmpty() && freshOrange > 0) {
    time++;
    // ...
}

while (!queue.isEmpty()) {
    int size = queue.size();
    boolean rottedThisMinute = false;

    for (int i = 0; i < size; i++) {
        // process...
        if (/* infected a neighbor */) {
            rottedThisMinute = true;
        }
    }

    if (rottedThisMinute) time++;  // Only count if actual infection happened
}

Grid: [[2,1,1],    Initial: 6 fresh oranges, 1 rotten at (0,0)
       [1,1,0],
       [0,1,1]]    Expected answer: 4 minutes

Initial: Queue=[(0,0)], fresh=6, time=0

Check: queue not empty && fresh>0 → TRUE
  time++ → time=1
  Process (0,0): infect (0,1), (1,0)
  fresh=4, Queue=[(0,1),(1,0)]

Check: queue not empty && fresh>0 → TRUE
  time++ → time=2
  Process (0,1): infect (0,2), (1,1)
  Process (1,0): nothing new
  fresh=2, Queue=[(0,2),(1,1)]

Check: queue not empty && fresh>0 → TRUE
  time++ → time=3
  Process (0,2): nothing (neighbor (1,2)=0)
  Process (1,1): infect (2,1)
  fresh=1, Queue=[(2,1)]

Check: queue not empty && fresh>0 → TRUE
  time++ → time=4
  Process (2,1): infect (2,2)
  fresh=0, Queue=[(2,2)]

Check: queue not empty && fresh>0 → FALSE (fresh=0)
  EXIT LOOP
  Return fresh==0 ? time : -1 → time=4 ✓ CORRECT!

...continuing from above...

Check: queue not empty → TRUE (Queue=[(2,2)])
  time++ → time=5  ← WRONG! Over-counting
  Process (2,2): no fresh neighbors
  Queue=[]

Return time=5 ✗ WRONG!

// LC 752 - Open the Lock
// IDEA: BFS on 4-digit combinations; each turn = 1 step
// time = O(10^4 * 4 * 2), space = O(10^4)
public int openLock(String[] deadends, String target) {
    Set<String> dead = new HashSet<>(Arrays.asList(deadends));
    Set<String> visited = new HashSet<>();
    Queue<String> queue = new LinkedList<>();
    String start = "0000";
    if (dead.contains(start)) return -1;
    queue.offer(start);
    visited.add(start);
    int steps = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            String curr = queue.poll();
            if (curr.equals(target)) return steps;
            char[] chars = curr.toCharArray();
            for (int j = 0; j < 4; j++) {
                char orig = chars[j];
                for (int delta : new int[]{1, -1}) {
                    chars[j] = (char)((orig - '0' + delta + 10) % 10 + '0');
                    String next = new String(chars);
                    if (!visited.contains(next) && !dead.contains(next)) {
                        visited.add(next); queue.offer(next);
                    }
                    chars[j] = orig;
                }
            }
        }
        steps++;
    }
    return -1;
}

index layout      swap table (neighbors of each index)
 0 1 2            0:[1,3]  1:[0,2,4]  2:[1,5]
 3 4 5            3:[0,4]  4:[1,3,5]  5:[2,4]

// java
// LC 773 - Sliding Puzzle
// time = O(6! * 6), space = O(6!)   at most 720 board states
// IDEA: state = flattened board string; BFS levels = number of moves
public int slidingPuzzle(int[][] board) {
    StringBuilder sb = new StringBuilder();
    for (int[] row : board) for (int v : row) sb.append(v);
    String start = sb.toString(), target = "123450";
    int[][] nbr = {{1,3},{0,2,4},{1,5},{0,4},{1,3,5},{2,4}};   // precomputed adjacency
    Queue<String> q = new LinkedList<>();
    Set<String> seen = new HashSet<>();
    q.offer(start); seen.add(start);
    int steps = 0;
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            String cur = q.poll();
            if (cur.equals(target)) return steps;
            int zero = cur.indexOf('0');
            for (int j : nbr[zero]) {              // slide a tile into the blank
                char[] arr = cur.toCharArray();
                char tmp = arr[zero]; arr[zero] = arr[j]; arr[j] = tmp;
                String next = new String(arr);
                if (seen.add(next)) q.offer(next);
            }
        }
        steps++;
    }
    return -1;                                     // target permutation unreachable
}

# python
# LC 773 - Sliding Puzzle
# time = O(6! * 6), space = O(6!)
# IDEA: BFS on the flattened board string, blank '0' swaps with its table neighbors
def slidingPuzzle(board):
    start = "".join(str(x) for row in board for x in row)
    target = "123450"
    nbr = [[1,3], [0,2,4], [1,5], [0,4], [1,3,5], [2,4]]
    q = deque([start])
    seen = {start}
    steps = 0
    while q:
        for _ in range(len(q)):
            cur = q.popleft()
            if cur == target:
                return steps
            i = cur.index('0')
            for j in nbr[i]:
                lst = list(cur)
                lst[i], lst[j] = lst[j], lst[i]
                nxt = "".join(lst)
                if nxt not in seen:
                    seen.add(nxt)
                    q.append(nxt)
        steps += 1
    return -1

// LC 130 - Surrounded Regions
// IDEA: BFS from border O-cells to find non-surrounded regions
// time = O(M*N), space = O(M*N)
public void solve(char[][] board) {
    int m = board.length, n = board[0].length;
    Queue<int[]> queue = new LinkedList<>();
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if ((i==0||i==m-1||j==0||j==n-1) && board[i][j]=='O') {
                board[i][j] = 'S'; queue.offer(new int[]{i,j});
            }
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    while (!queue.isEmpty()) {
        int[] c = queue.poll();
        for (int[] d : dirs) {
            int nr=c[0]+d[0], nc=c[1]+d[1];
            if (nr>=0&&nr<m&&nc>=0&&nc<n&&board[nr][nc]=='O') {
                board[nr][nc]='S'; queue.offer(new int[]{nr,nc});
            }
        }
    }
    for (int i=0;i<m;i++) for (int j=0;j<n;j++)
        board[i][j] = board[i][j]=='S' ? 'O' : (board[i][j]=='O' ? 'X' : board[i][j]);
}

// LC 207 - Course Schedule
// IDEA: Kahn's BFS topological sort — detect cycle in directed graph
// time = O(V+E), space = O(V+E)
public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[] inDegree = new int[numCourses];
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
    for (int[] pre : prerequisites) {
        adj.get(pre[1]).add(pre[0]);
        inDegree[pre[0]]++;
    }
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) if (inDegree[i] == 0) queue.offer(i);
    int processed = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        processed++;
        for (int next : adj.get(course))
            if (--inDegree[next] == 0) queue.offer(next);
    }
    return processed == numCourses;
}

// LC 286 - Walls and Gates
// IDEA: Multi-source BFS from all gates — propagate distances
// time = O(M*N), space = O(M*N)
public void wallsAndGates(int[][] rooms) {
    int m = rooms.length, n = rooms[0].length;
    int INF = Integer.MAX_VALUE;
    Queue<int[]> queue = new LinkedList<>();
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (rooms[i][j] == 0) queue.offer(new int[]{i, j});
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        for (int[] d : dirs) {
            int nr = cell[0]+d[0], nc = cell[1]+d[1];
            if (nr>=0&&nr<m&&nc>=0&&nc<n&&rooms[nr][nc]==INF) {
                rooms[nr][nc] = rooms[cell[0]][cell[1]] + 1;
                queue.offer(new int[]{nr, nc});
            }
        }
    }
}

Example: 0 - 1 - 2 - 3 - 4

Layer 1: remove 0, 4  (leaves)
Layer 2: remove 1, 3  (new leaves)
Result:  [2] ✅        (centroid)

// LC 310 - Minimum Height Trees
// IDEA: BFS leaf trimming with degree array
// time = O(N), space = O(N)
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    if (n == 1) return Collections.singletonList(0);

    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    int[] degree = new int[n];

    for (int[] e : edges) {
        graph.get(e[0]).add(e[1]);
        graph.get(e[1]).add(e[0]);
        degree[e[0]]++;
        degree[e[1]]++;
    }

    Queue<Integer> leaves = new LinkedList<>();
    for (int i = 0; i < n; i++)
        if (degree[i] == 1) leaves.offer(i);

    int remaining = n;
    while (remaining > 2) {
        int size = leaves.size();
        remaining -= size;
        for (int i = 0; i < size; i++) {
            int leaf = leaves.poll();
            for (int nei : graph.get(leaf)) {
                degree[nei]--;
                if (degree[nei] == 1) leaves.offer(nei);
            }
        }
    }
    return new ArrayList<>(leaves);
}

// LC 310 - Using Set for adjacency
// time = O(N), space = O(N)
public List<Integer> findMinHeightTrees_set(int n, int[][] edges) {
    if (n == 1) return Collections.singletonList(0);
    List<Set<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new HashSet<>());
    for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
    Queue<Integer> leaves = new LinkedList<>();
    for (int i = 0; i < n; i++) if (adj.get(i).size() == 1) leaves.offer(i);
    int remaining = n;
    while (remaining > 2) {
        int size = leaves.size();
        remaining -= size;
        for (int i = 0; i < size; i++) {
            int leaf = leaves.poll();
            int neighbor = adj.get(leaf).iterator().next();
            adj.get(neighbor).remove(leaf);
            if (adj.get(neighbor).size() == 1) leaves.offer(neighbor);
        }
    }
    return new ArrayList<>(leaves);
}

// LC 909 - Snakes and Ladders
// IDEA: BFS — each square is a node, dice roll = edges
// time = O(N^2), space = O(N^2)
public int snakesAndLadders(int[][] board) {
    int n = board.length;
    int[] flat = new int[n * n + 1];
    int idx = 1; boolean leftToRight = true;
    for (int r = n-1; r >= 0; r--) {
        if (leftToRight) for (int c = 0; c < n; c++) flat[idx++] = board[r][c];
        else for (int c = n-1; c >= 0; c--) flat[idx++] = board[r][c];
        leftToRight = !leftToRight;
    }
    boolean[] visited = new boolean[n*n+1];
    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{1, 0});
    visited[1] = true;
    while (!queue.isEmpty()) {
        int[] curr = queue.poll();
        int pos = curr[0], steps = curr[1];
        for (int dice = 1; dice <= 6 && pos+dice <= n*n; dice++) {
            int next = pos + dice;
            if (flat[next] != -1) next = flat[next];
            if (next == n*n) return steps + 1;
            if (!visited[next]) { visited[next] = true; queue.offer(new int[]{next, steps+1}); }
        }
    }
    return -1;
}

// LC 417 - Pacific Atlantic Water Flow
// IDEA: BFS from Pacific border + Atlantic border; intersection = answer
// time = O(M*N), space = O(M*N)
public List<List<Integer>> pacificAtlantic(int[][] heights) {
    int m = heights.length, n = heights[0].length;
    boolean[][] pac = new boolean[m][n], atl = new boolean[m][n];
    Queue<int[]> pq = new LinkedList<>(), aq = new LinkedList<>();
    for (int i = 0; i < m; i++) {
        pq.offer(new int[]{i,0}); pac[i][0]=true;
        aq.offer(new int[]{i,n-1}); atl[i][n-1]=true;
    }
    for (int j = 0; j < n; j++) {
        pq.offer(new int[]{0,j}); pac[0][j]=true;
        aq.offer(new int[]{m-1,j}); atl[m-1][j]=true;
    }
    bfs(heights, pq, pac, m, n);
    bfs(heights, aq, atl, m, n);
    List<List<Integer>> res = new ArrayList<>();
    for (int i=0;i<m;i++) for (int j=0;j<n;j++)
        if (pac[i][j]&&atl[i][j]) res.add(Arrays.asList(i,j));
    return res;
}
private void bfs(int[][] h, Queue<int[]> q, boolean[][] visited, int m, int n) {
    int[][] dirs={{1,0},{-1,0},{0,1},{0,-1}};
    while (!q.isEmpty()) {
        int[] c=q.poll();
        for (int[] d:dirs) {
            int nr=c[0]+d[0],nc=c[1]+d[1];
            if (nr>=0&&nr<m&&nc>=0&&nc<n&&!visited[nr][nc]&&h[nr][nc]>=h[c[0]][c[1]]) {
                visited[nr][nc]=true; q.offer(new int[]{nr,nc});
            }
        }
    }
}

// LC 279 - Perfect Squares
// IDEA: BFS — treat each number as a node, edges = subtracting a perfect square
// time = O(N * sqrt(N)), space = O(N)
public int numSquares(int n) {
    // Pre-calculate perfect squares up to n
    List<Integer> squares = new ArrayList<>();
    for (int i = 1; i * i <= n; i++) {
        squares.add(i * i);
    }

    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();

    queue.offer(n);
    visited.add(n);

    int level = 0;

    while (!queue.isEmpty()) {
        level++;
        int size = queue.size();

        for (int i = 0; i < size; i++) {
            int remaining = queue.poll();

            for (int square : squares) {
                int nextVal = remaining - square;

                if (nextVal == 0)
                    return level; // Found shortest path
                if (nextVal < 0)
                    break; // Squares are sorted, so we can stop

                if (!visited.contains(nextVal)) {
                    visited.add(nextVal);
                    queue.offer(nextVal);
                }
            }
        }
    }
    return -1;
}

# python — LC 742 (DFS build graph + BFS from target)
from collections import defaultdict, deque

class Solution(object):
    def findClosestLeaf(self, root, k):
        graph = defaultdict(list)   # node -> [neighbors]  (undirected)
        leaves = set()
        target = [None]

        def build(node, parent):
            if not node:
                return
            if node.val == k:
                target[0] = node
            if parent:                          # connect BOTH directions
                graph[node].append(parent)
                graph[parent].append(node)
            if not node.left and not node.right: # leaf = no children
                leaves.add(node)
            build(node.left, node)
            build(node.right, node)

        build(root, None)

        # BFS from target; first leaf reached is the closest
        q = deque([target[0]])
        visited = {target[0]}
        while q:
            node = q.popleft()
            if node in leaves:
                return node.val                  # earliest pop = fewest edges
            for nei in graph[node]:
                if nei not in visited:
                    visited.add(nei)
                    q.append(nei)

Tree (k=2):                 As undirected graph, BFS from 2:
       1                    dist 0: 2
      / \                   dist 1: 4, 1
     2   3   (leaf)         dist 2: 5, 3(leaf) <- returned (3 closer than the 5→6 chain)
    /
   4
  /
 5
/
6 (leaf)

# python — LC 116/117: BFS by layer, chain nodes via prev pointer
from collections import deque

class Solution(object):
    def connect(self, root):
        # time = O(N), space = O(W)  (W = max width / one level)
        if not root:
            return None

        q = deque([root])
        while q:
            size = len(q)
            prev = None
            for _ in range(size):          # one full level per outer iteration
                cur = q.popleft()
                if prev:                    # link previous node -> current
                    prev.next = cur
                prev = cur
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
            prev.next = None                # last node of the level -> NULL
        return root

# python — same BFS, use i < size - 1 to point at the next node still in queue
for i in range(size):
    cur = q.popleft()
    if i < size - 1:
        cur.next = q[0]                     # front of queue = node to the right
    if cur.left:  q.append(cur.left)
    if cur.right: q.append(cur.right)

# python — walk each level as a linked list to wire the next level
class Solution(object):
    def connect(self, root):
        # time = O(N), space = O(1)
        if not root:
            return None
        leftmost = root
        while leftmost.left:               # stop once we reach the leaf level
            head = leftmost
            while head:
                head.left.next = head.right             # (1) same parent
                if head.next:
                    head.right.next = head.next.left    # (2) across parents
                head = head.next                        # move right via existing links
            leftmost = leftmost.left        # drop to next level's leftmost
        return root

Visual (LC 116):
        1 -> NULL
      /   \
     2  -> 3 -> NULL
    / \   / \
   4-> 5->6->7 -> NULL

BFS level 2: prev walks 4→5→6→7, chaining next; last (7) -> NULL.
O(1) trick: from level [2,3], (1) 2.left→2.right = 4→5, (2) 2.right→2.next.left = 5→6, ...

# python — LC 623 Add One Row to Tree (level BFS, stop at depth-1)
# time = O(N), space = O(W)   N = #nodes, W = max level width
from collections import deque

class Solution(object):
    def addOneRow(self, root, val, depth):
        # (1) no `depth - 1` row exists -> new node becomes the new root
        if depth == 1:
            new_root = TreeNode(val)
            new_root.left = root
            return new_root

        q = deque([root])
        cur_depth = 1                       # root is at depth 1 (NOT 0)

        while q:
            size = len(q)

            # NOTE !!! treat `cur_depth == depth - 1` as a SEPARATE path:
            #          inside it we rewire instead of descending, then stop
            if cur_depth == depth - 1:
                for _ in range(size):
                    node = q.popleft()

                    old_left = node.left     # (2) cache BEFORE overwriting
                    old_right = node.right

                    node.left = TreeNode(val)   # (3) splice the new row in
                    node.right = TreeNode(val)

                    node.left.left = old_left   # (4) reattach on OUTER sides
                    node.right.right = old_right
                break                        # (5) done — never descend further

            # otherwise: ordinary level-order descent
            for _ in range(size):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)

            cur_depth += 1

        return root

# python — branch per node instead of per level; break after the level finishes
while q:
    size = len(q)
    for _ in range(size):
        node = q.popleft()
        if cur_depth == depth - 1:
            old_left, old_right = node.left, node.right
            node.left, node.right = TreeNode(val), TreeNode(val)
            node.left.left = old_left
            node.right.right = old_right
        else:
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)

    if cur_depth == depth - 1:   # break AFTER the whole level is rewired
        break
    cur_depth += 1

# python — recurse down to d == 2, then rewire that node's children
# time = O(N), space = O(h)
class Solution(object):
    def addOneRow(self, root, v, d):
        if not root:
            return None
        if d == 1:                                   # new root
            new_root = TreeNode(v)
            new_root.left = root
            return new_root
        if d == 2:                                   # root IS the depth-1 parent
            root.left,  root.left.left   = TreeNode(v), root.left
            root.right, root.right.right = TreeNode(v), root.right
            return root
        root.left  = self.addOneRow(root.left,  v, d - 1)
        root.right = self.addOneRow(root.right, v, d - 1)
        return root

Visual — root = [4,2,6,3,1,5], val = 1, depth = 2   (rewire level depth-1 = 1, i.e. node 4)

before                    cache 4's children       after (new row of 1s)
      4                   old_left  = 2                  4
     / \                  old_right = 6                 / \
    2   6                                              1   1
   / \   \                4.left  = new 1              /     \
  3   1   5               4.right = new 1             2       6
                          1.left  = 2  (outer)       / \       \
                          1.right = 6  (outer)      3   1       5

depth == 1 case: brand-new node becomes root, whole old tree hangs on its LEFT.

# python — shape B: expand exactly k levels, then the queue IS the answer
# (no distance stored; naturally returns [] when the tree is smaller than k)
# time = O(n), space = O(n)
class Solution(object):
    def distanceK(self, root, target, k):
        parents = {}
        def add_parents(node, parent):
            if not node:
                return
            parents[node] = parent
            add_parents(node.left, node)
            add_parents(node.right, node)
        add_parents(root, None)

        q = collections.deque([target])
        visited = {target}
        for _ in range(k):                     # k full level expansions
            for _ in range(len(q)):            # snapshot the level size FIRST
                node = q.popleft()
                for nxt in (node.left, node.right, parents[node]):
                    if nxt and nxt not in visited:
                        visited.add(nxt)
                        q.append(nxt)
        return [node.val for node in q]        # everything left is exactly k away

// java — shape B: k level expansions, remaining queue = answer
// LC 863 - All Nodes Distance K in Binary Tree
// time = O(n), space = O(n)
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
    Map<TreeNode, TreeNode> parents = new HashMap<>();
    build(root, null, parents);

    Queue<TreeNode> q = new LinkedList<>();
    q.offer(target);
    Set<TreeNode> visited = new HashSet<>();
    visited.add(target);

    for (int step = 0; step < k; step++) {
        int size = q.size();                    // snapshot: level boundary
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            for (TreeNode nei : new TreeNode[]{node.left, node.right, parents.get(node)}) {
                if (nei != null && visited.add(nei)) q.offer(nei);
            }
        }
    }
    List<Integer> ans = new ArrayList<>();
    for (TreeNode node : q) ans.add(node.val);  // may be empty → correct
    return ans;
}

private void build(TreeNode node, TreeNode parent, Map<TreeNode, TreeNode> parents) {
    if (node == null) return;
    parents.put(node, parent);
    build(node.left, node, parents);
    build(node.right, node, parents);
}