ลูกพี่ลูกน้องในต้นไม้ไบนารีใน C++

สมมติว่าเรามีต้นไม้ไบนารี โหนดรากอยู่ที่ระดับ 0 และลูกของโหนดที่ระดับ k จะอยู่ที่ระดับ k+1

โหนดสองโหนดในต้นไม้ไบนารีเรียกว่า "ลูกพี่ลูกน้อง" ถ้าพวกเขาอยู่ที่ระดับเดียวกัน แต่มีพ่อแม่วย่างคนละคน

ค่าทั้งหมดในต้นไม้จะไม่ซ้ำกัน และมีค่า x และ y ของโหนดสองโหนดที่ต่างกัน เราต้องตรวจสอบว่าโหนดที่ตรงกับค่า x และ y เป็นลูกพี่ลูกน้องกันหรือไม่

เช่น ถ้าอินพุตเป็น:

x = 5, y = 4 ผลลัพธ์จะเป็น true

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:

• กำหนดแมป um

• กำหนดคิว q

• เพิ่มรากเข้า q

• um[x] := um[y] := null

• ทำซ้ำ while (q ไม่ว่าง):

  • qSize := ขนาดของ q

  • ทำซ้ำ while qSize > 0 (ลด qSize ลง 1):

    • cur := องค์ประกอบแรกของ q

    • ลบองค์ประกอบออกจาก q

    • ถ้าลูกซ้ายของ cur มีอยู่ ให้:

      • ถ้า 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