資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告