数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中的二叉树堂兄弟节点
假设我们有一个二叉树，根节点位于深度 0，每个深度 k 节点的子节点位于深度 k+1。
这里，二叉树中的两个节点如果具有相同的深度，但具有不同的父节点，则被称为堂兄弟节点。
树的所有值都是唯一的，并且树中两个不同节点的值为 x 和 y。我们需要检查对应于值 x 和 y 的节点是否是堂兄弟节点。
因此，如果输入类似于
x = 5，y = 4，则输出将为 true
为了解决这个问题，我们将遵循以下步骤：
定义一个映射 um
定义一个队列 q
将根节点插入到 q 中
um[x] := um[y] := null
当 (q 不为空) 时，执行：
qSize := q 的大小
当 qSize > 0 时（将 qSize 减 1），执行：
cur := q 的第一个元素
从 q 中删除元素
如果 curr 的左子节点存在，则：
如果 um 包含 cur 的左子节点的值，则
um[cur 的左子节点的值] := cur
否则
将 cur 的左子节点插入到 q 中
如果 um 包含 cur 的右子节点的值，则
um[cur 的右子节点的值] := cur
否则
将 cur 的右子节点插入到 q 中
如果 um[x] 或 um[y] 不为零，则：
如果 um[x] 为 0 或 um[y] 为 0 或 um[x] 与 um[y] 相同，则：
返回 false
否则
返回 true
返回 false
示例
让我们查看以下实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) {
val = data;
left = NULL;
right = NULL;
}
};
class Solution {
public:
bool isCousins(TreeNode *root, int x, int y) {
unordered_map<int, TreeNode *> um;
queue<TreeNode *> q;
q.push(root);
um[x] = um[y] = NULL;
while (!q.empty()) {
int qSize = q.size();
while (qSize-- > 0) {
auto cur = q.front();
q.pop();
if (cur->left && cur->left->val != 0)
if (um.count(cur->left->val))
um[cur->left->val] = cur;
else
q.push(cur->left);
if (cur->right && cur->right->val != 0)
if (um.count(cur->right->val))
um[cur->right->val] = cur;
else
q.push(cur->right);
}
if (um[x] or um[y])
if (!um[x] or !um[y] or um[x] == um[y])
return false;
else
return true;
}
return false;
}
};
main() {
Solution ob;
TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2); root->right = new TreeNode(3);
root->left->right = new TreeNode(4); root->right->right = new TreeNode(5);
cout << (ob.isCousins(root, 5, 4));
}输入
TreeNode *root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->right = new TreeNode(4); root->right->right = new TreeNode(5); cout << (ob.isCousins(root, 5, 4));
输出
1
更新于： 2020-11-16
467 次查看
广告