Approach 1: Annotate Parent and Depth
Nodes are cousins if they have the same depth but different parents. A straightforward approach is to be able to know the parent and depth of each node.
We can use a depth-first search to annotate each node. For each
node with parent
par and depth
d, we will record results in hashmaps:
parent[node.val] = par and
depth[node.val] = d.
Time Complexity: , where is the number of nodes in the tree.
Space Complexity: .
Analysis written by: @awice.