解决方案
方法一:标记父节点与深度
思路
一对节点是堂兄弟节点当且仅当它们拥有相同的深度且父节点不相同。一种非常直接的方法就是通过某种方法求出每一个节点的深度与父节点。
算法
我们用深度优先遍历标记每一个节点,对于每一个节点 node,它的父亲为 par,深度为 d,我们将其记录到 Hashmap 中:parent[node.val] = par 与 depth[node.val] = d。
复杂度分析
-
时间复杂度:,其中 是给定树中节点的数量。
-
空间复杂度:。
在二叉树中,根节点位于深度 0 处,每个深度为 k 的节点的子节点位于深度 k+1 处。
如果二叉树的两个节点深度相同,但 父节点不同 ,则它们是一对堂兄弟节点。
我们给出了具有唯一值的二叉树的根节点 root ,以及树中两个不同节点的值 x 和 y 。
只有与值 x 和 y 对应的节点是堂兄弟节点时,才返回 true 。否则,返回 false。
示例 1:

输入:root = [1,2,3,4], x = 4, y = 3 输出:false
示例 2:

输入:root = [1,2,3,null,4,null,5], x = 5, y = 4 输出:true
示例 3:

输入:root = [1,2,3,null,4], x = 2, y = 3 输出:false
提示:
2 到 100 之间。1 到 100 的整数。