解决方案
方法一:标记父节点与深度
思路
一对节点是堂兄弟节点当且仅当它们拥有相同的深度且父节点不相同。一种非常直接的方法就是通过某种方法求出每一个节点的深度与父节点。
算法
我们用深度优先遍历标记每一个节点,对于每一个节点 node
,它的父亲为 par
,深度为 d
,我们将其记录到 Hashmap
中:parent[node.val] = par
与 depth[node.val] = d
。
复杂度分析
-
时间复杂度:,其中 是给定树中节点的数量。
-
空间复杂度:。