สมมติว่าเรามีไบนารีทรี รูทโหนดอยู่ที่ระดับความลึก 0 และโหนดย่อยของแต่ละโหนดความลึก k อยู่ที่ระดับความลึก k+1
ในที่นี้โหนดสองโหนดของไบนารีทรีจะเรียกว่าลูกพี่ลูกน้องหากมีความลึกเท่ากัน แต่มีพาเรนต์ต่างกัน
ค่าทั้งหมดของทรีจะไม่ซ้ำกัน และค่า x และ y ของโหนดที่ต่างกันสองโหนดในทรี เราต้องตรวจสอบว่าโหนดที่สอดคล้องกับค่า x และ y เป็นลูกพี่ลูกน้องหรือไม่
ดังนั้นหากอินพุตเป็นแบบ
x =5, y =4 แล้วผลลัพธ์จะเป็นจริง
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดหนึ่งแผนที่ um
-
กำหนดหนึ่งคิว q
-
แทรกรูทลงใน q
-
อืม[x] :=อืม[y] :=null
-
ในขณะที่ (ไม่ใช่ q ว่างเปล่า) ทำ -
-
qSize :=ขนาดของ q
-
ในขณะที่ qSize> 0 จากนั้น (ลดขนาด qSize ลง 1) ให้ทำ -
-
cur :=องค์ประกอบแรกของ q
-
ลบองค์ประกอบออกจาก q
-
หากมีเหลือของสกุลเงิน −
-
ถ้า um มีค่า left of cur แล้ว
-
um[value of left of cur] :=cur
-
-
มิฉะนั้น
-
แทรกด้านซ้ายของ cur ลงใน q
-
-
ถ้า um มีค่าของ cur แล้ว
-
อืม[ค่าของสิทธิของเคอร์] :=cur
-
-
มิฉะนั้น
-
แทรกด้านขวาของ cur ลงใน q
-
-
-
ถ้า um[x] หรือ um[y] ไม่ใช่ศูนย์ ดังนั้น −
-
ถ้า um[x] เป็น 0 หรือ um[y] เป็น 0 หรือ um[x] เหมือนกับ um[y] ดังนั้น −
-
คืนค่าเท็จ
-
-
มิฉะนั้น
-
คืนความจริง
-
-
-
-
-
คืนค่าเท็จ
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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
