468. Cousin Nodes
A family tree is stored as a binary tree rooted at root, where every member has a distinct integer id. The root has depth 0 and each child is one level deeper than its parent. Two different members are cousins when they sit at the same depth but have different parents.
Given the ids x and y of two members, return true if they are cousins and false otherwise. Siblings (members with the same parent) are not cousins, and neither are members at different depths. Both ids are guaranteed to appear in the tree and x differs from y.
Example 1
- Input:
- root = [1,2,3,4,null,null,5], x = 4, y = 5
- Output:
- true
- Explanation:
Nodes 4 and 5 are both at depth 2 and have different parents (2 and 3), so they are cousins.
Example 2
- Input:
- root = [1,2,3,4,null,null,5], x = 2, y = 3
- Output:
- false
- Explanation:
Nodes 2 and 3 share the same depth but also the same parent 1, so they are siblings, not cousins.
Example 3
- Input:
- root = [1,2,3,4,null,null,5], x = 4, y = 3
- Output:
- false
- Explanation:
Node 4 is at depth 2 while node 3 is at depth 1, so they are not cousins.
Constraints
2 ≤ number of nodes in root ≤ 1000
-10000 ≤ Node.val ≤ 10000, all values are distinct
x ≠ y, and both x and y are values present in the tree
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(w)