993.二叉树的堂兄弟节点

发表于 | 分类于
字数统计: 536 | 阅读时长 ≈ 2

一、题目描述

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

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

我们给出了具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x 和 y。

只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 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. 二叉树的节点数介于 2 到 100 之间。
  2. 每个节点的值都是唯一的、范围为 1 到 100 的整数。

二、题解

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;
}