What is the time complexity of the Reachable Nodes With Restrictions problem?

The time complexity is typically O(n) where n is the number of nodes in the tree, due to the single traversal of the tree.

What pattern is used to solve the Reachable Nodes With Restrictions problem?

The solution relies on array scanning combined with hash lookup for efficient node checking and traversal.

How do you handle restricted nodes during the traversal?

By maintaining a hash set of restricted nodes, you can efficiently check during traversal whether a node is restricted and skip it if necessary.

Can the solution be optimized further?

Yes, early stopping can be implemented to terminate the traversal once all reachable nodes have been visited, improving efficiency.

Is BFS or DFS better for this problem?

Both BFS and DFS are valid approaches, but the choice depends on the specific problem constraints and preference for iterative versus recursive solutions.

#2368

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

受限条件下可到达节点的数目

现有一棵由 n 个节点组成的无向树，节点编号从 0 到 n - 1 ，共有 n - 1 条边。给你一个二维整数数组 edges ，长度为 n - 1 ，其中 edges[i] = [a i , b i ] 表示树中节点 a i 和 b i 之间存在一条边。另给你一个整数数组 restricted …

数组哈希表树深度优先搜索广度优先搜索

题目描述

现有一棵由 n 个节点组成的无向树，节点编号从 0 到 n - 1 ，共有 n - 1 条边。

给你一个二维整数数组 edges ，长度为 n - 1 ，其中 edges[i] = [a_i, b_i] 表示树中节点 a_i 和 b_i 之间存在一条边。另给你一个整数数组 restricted 表示受限节点。

在不访问受限节点的前提下，返回你可以从节点 0 到达的最多节点数目。

注意，节点 0 不会标记为受限节点。

示例 1：

输入：n = 7, edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted = [4,5]
输出：4
解释：上图所示正是这棵树。
在不访问受限节点的前提下，只有节点 [0,1,2,3] 可以从节点 0 到达。

示例 2：

输入：n = 7, edges = [[0,1],[0,2],[0,5],[0,4],[3,2],[6,5]], restricted = [4,2,1]
输出：3
解释：上图所示正是这棵树。
在不访问受限节点的前提下，只有节点 [0,5,6] 可以从节点 0 到达。

提示：

2 <= n <= 10⁵
edges.length == n - 1
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
edges 表示一棵有效的树
1 <= restricted.length < n
1 <= restricted[i] < n
restricted 中的所有值 互不相同

lightbulb

解题思路

方法一：DFS

我们首先根据给定的边构建一个邻接表 $g$ ，其中 $g[i]$ 表示与节点 $i$ 相邻的节点列表。然后我们定义一个哈希表 $vis$ ，用于记录受限节点或者已经访问过的节点，初始时将受限节点加入到 $vis$ 中。

接下来我们定义一个深度优先搜索函数 $dfs(i)$ ，表示从节点 $i$ 出发，可以到达的节点数。在 $dfs(i)$ 函数中，我们首先将节点 $i$ 加入到 $vis$ 中，然后遍历节点 $i$ 的相邻节点 $j$ ，如果 $j$ 不在 $vis$ 中，我们递归调用 $dfs(j)$ ，并将返回值加到结果中。

最后我们返回 $dfs(0)$ 即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为节点数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def reachableNodes(
        self, n: int, edges: List[List[int]], restricted: List[int]
    ) -> int:
        def dfs(i: int) -> int:
            vis.add(i)
            return 1 + sum(j not in vis and dfs(j) for j in g[i])

        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        vis = set(restricted)
        return dfs(0)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate shows an understanding of tree traversal techniques like DFS or BFS.
question_mark
Candidate is able to use hash sets for efficient lookups, avoiding restricted nodes.
question_mark
Candidate demonstrates optimization skills by considering early termination in traversal.

warning

常见陷阱

外企场景

error
Failing to correctly handle the restricted nodes, causing the traversal to incorrectly include invalid nodes.
error
Incorrectly managing the visited set, leading to cycles or revisiting nodes.
error
Not optimizing the traversal, leading to unnecessary checks or excessive computation.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if there are additional restrictions such as time limits on traversal?
arrow_right_alt
Can this problem be solved with a Union-Find approach instead of DFS or BFS?
arrow_right_alt
How would the solution change if there were multiple starting nodes?

help

常见问题

外企场景

继续练习

#2421 好路径的数目 #2467 树上最大得分和路径 #3493 属性图