Sponsored
Sponsored
Performing Depth-First Search (DFS) is a common way to traverse a tree or graph. We'll start from node 0 and explore as far as possible along each branch before backtracking, avoiding restricted nodes and those already visited.
Time Complexity: O(n) because each node is visited once.
Space Complexity: O(n) for storing the adjacency list and visited nodes information.
1import java.util.*;
2
3class Solution {
4 public int reachableNodes(int n, int[][] edges, int[] restricted) {
5 Set<Integer> restrictedSet = new HashSet<>();
6 for (int r : restricted) restrictedSet.add(r);
7 Map<Integer, List<Integer>> adjList = new HashMap<>();
8 for (int i = 0; i < n; i++) adjList.put(i, new ArrayList<>());
9 for (int[] edge : edges) {
10 adjList.get(edge[0]).add(edge[1]);
11 adjList.get(edge[1]).add(edge[0]);
12 }
13 return dfs(0, adjList, restrictedSet, new boolean[n]);
14 }
15
16 private int dfs(int node, Map<Integer, List<Integer>> adjList, Set<Integer> restricted, boolean[] visited) {
17 if (restricted.contains(node) || visited[node])
18 return 0;
19 visited[node] = true;
20 int count = 1;
21 for (int neighbor : adjList.get(node)) {
22 count += dfs(neighbor, adjList, restricted, visited);
23 }
24 return count;
25 }
26}This Java solution constructs an adjacency list using a HashMap. The DFS explores from node 0 and keeps track of visited nodes using a boolean array, skipping any restricted nodes.
Breadth-First Search (BFS) can also be used to traverse the tree level-by-level. Starting from node 0, visit all neighbors at the current depth before moving on to nodes at the next depth level, while skipping restricted nodes.
Time Complexity: O(n) because each node is processed once using BFS.
Space Complexity: O(n) for adjacency list and other arrays.
1
JavaScript's implementation uses an array as a queue to perform BFS. The method starts at node 0 and progresses level by level, skipping over restricted nodes and tracking visited nodes.