N-ary Tree Cousins
EasyTree · Adobe
A rooted tree with n nodes labeled 0 to n - 1 is given as a parent array: parent[i] is the parent of node i, and the root is the single node whose parent is -1 (the root is not necessarily node 0). A node may have any number of children.
The root has depth 0, and every other node is one deeper than its parent. Two nodes are cousins if they have the same depth but different parents. Siblings (same parent) are not cousins, and a node is not its own cousin.
Given two node labels x and y, return True if they are cousins and False otherwise.
Example 1
- Input:
- parent = [3, 3, 0, -1, 1, 2, 2], x = 4, y = 2
- Output:
- True
- Explanation
- Node 3 is the root, with children 0 and 1. Node 2 hangs under 0 and node 4 under 1, so both are at depth 2 with different parents: cousins.
Example 2
- Input:
- parent = [3, 3, 0, -1, 1, 2, 2], x = 5, y = 6
- Output:
- False
- Explanation
- Nodes 5 and 6 are both at depth 3, but they share parent 2, so they are siblings rather than cousins.
Example 3
- Input:
- parent = [3, 3, 0, -1, 1, 2, 2], x = 4, y = 5
- Output:
- False
- Explanation
- Node 4 is at depth 2 and node 5 is at depth 3, so they cannot be cousins.
Constraints
1 <= parent.length <= 10^5- Exactly one
parent[i]is-1, andparentdescribes a single valid rooted tree 0 <= x, y < parent.length