Preorder Traversal Without Invalid Nodes

Examples

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], root = 0, invalid = [1,6]

Output: [0,3,4,2,5]

Explanation:

Example 2:

Input: n = 5, edges = [[0,1],[0,2],[1,3],[1,4]], root = 0, invalid = [0,4]

Output: [1,3,2]

Explanation:

You are given a rooted tree with n nodes labeled from 0 to n - 1, represented by directed edges edges, where edges[i] = [parent, child].

You are also given the root node and an array invalid containing nodes that are marked invalid.

Return the preorder traversal of the tree, excluding invalid nodes.

Traversal rules:

Visit a node before its children (preorder).
Children must be visited in the same order as they appear in edges.
If a node is invalid, do not include it in the output, but still continue traversing its children.

Preorder visits 0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6. Nodes 1 and 6 are skipped from output.

0 is invalid so it is omitted, but traversal still continues through its children.

1 <= n <= 10^5

edges.length == n - 1

0 <= parent, child < n

Input edges always form a valid rooted tree.

0 <= root < n

0 <= invalid.length <= n

0 <= invalid[i] < n

invalid contains unique node IDs.