There is an undirected tree with n nodes labeled from 0 to n - 1 and n - 1 edges.
You are given a 2D integer array edges of length n - 1 where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. You are also given an integer array restricted which represents restricted nodes.
Return the maximum number of nodes you can reach from node 0 without visiting a restricted node.
Note that node 0 will not be a restricted node.
Example 1:
Input: n = 7, edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted = [4,5] Output: 4 Explanation: The diagram above shows the tree. We have that [0,1,2,3] are the only nodes that can be reached from node 0 without visiting a restricted node.
Example 2:
Input: n = 7, edges = [[0,1],[0,2],[0,5],[0,4],[3,2],[6,5]], restricted = [4,2,1] Output: 3 Explanation: The diagram above shows the tree. We have that [0,5,6] are the only nodes that can be reached from node 0 without visiting a restricted node.
Constraints:
2 <= n <= 105edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != biedges represents a valid tree.1 <= restricted.length < n1 <= restricted[i] < nrestricted are unique.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.
This approach builds an adjacency list from the input edges, then performs a DFS starting from node 0. It skips over restricted nodes and ensures each node is visited only once. The count of nodes reached is returned as the answer.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) because each node is visited once.
Space Complexity: O(n) for storing the adjacency list and visited nodes information.
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.
This BFS approach uses an adjacency list and a queue to explore the tree level-by-level. It checks each neighbor for restrictions and previously visited status before enqueuing it.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) because each node is processed once using BFS.
Space Complexity: O(n) for adjacency list and other arrays.
| Approach | Complexity |
|---|---|
| DFS Approach Using Adjacency List | Time Complexity: O(n) because each node is visited once. |
| BFS Approach Using Adjacency List | Time Complexity: O(n) because each node is processed once using BFS. |
Leetcode 2368. Reachable Nodes With Restrictions | WeeklyContest 305. Medium • Code with Alisha • 1,414 views views
Watch 9 more video solutions →Practice Reachable Nodes With Restrictions with our built-in code editor and test cases.
Practice on FleetCode