993.二叉树的堂兄弟节点

一、题目描述

在二叉树中,根节点位于深度 0 处,每个深度为 k 的节点的子节点位于深度 k+1 处。

如果二叉树的两个节点深度相同,但父节点不同,则它们是一对堂兄弟节点

我们给出了具有唯一值的二叉树的根节点 root,以及树中两个不同节点的值 xy

只有与值 xy 对应的节点是堂兄弟节点时,才返回 true。否则,返回 false

示例 1:
1.png

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

示例 2:
2.png

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

示例 3:

3.png

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

提示:

  1. 二叉树的节点数介于 2100 之间。
  2. 每个节点的值都是唯一的、范围为 1100 的整数。

二、题解

1.递归

1.1 思路

关键信息:堂兄弟节点的定义:深度相同,父节点不同

  1. 使用辅助函数,求x和y的深度及其父节点
  2. 由于辅助函数执行完毕后,会释放函数内部变量的内存空间,参考了评论中一位大神的题解,可以使用结构体存储深度和父节点
  3. 递归调用help()函数即可

1.2 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
//深度相同,父节点不同
typedef struct Node
{
int deepth;
struct TreeNode *father;
} Node;
//求深度和父节点
help(struct TreeNode *root, int val, int deepth, struct TreeNode *father, struct Node *node)
{
if (!root)
return;
if (root->val == val)
{
node->father = father;
node->deepth = deepth;
}
else
{
help(root->left, val, deepth + 1, root, node);
help(root->right, val, deepth + 1, root, node);
}
}

bool isCousins(struct TreeNode *root, int x, int y)
{
struct Node *node1 = (struct Node *)malloc(sizeof(struct Node));
struct Node *node2 = (struct Node *)malloc(sizeof(struct Node));
node1->deepth = 0;
node1->father = NULL;
node2->deepth = 0;
node2->father = NULL;
help(root, x, 0, NULL, node1);
help(root, y, 0, NULL, node2);
printf("%d", node1->deepth);
printf("%d", node2->deepth);
return node1->deepth == node2->deepth && node1->father != node2->father;
}