Anh em họ trong Cây nhị phân trong C ++

Giả sử chúng ta có một cây nhị phân, nút gốc có ở độ sâu 0 và nút con của mỗi nút độ sâu k ở độ sâu k + 1.

Ở đây, hai nút của cây nhị phân được gọi là anh em họ nếu chúng có cùng độ sâu, nhưng có cha mẹ khác nhau.

Tất cả các giá trị của cây sẽ là duy nhất và các giá trị x và y của hai nút khác nhau trong cây. Chúng ta phải kiểm tra xem các nút tương ứng với các giá trị x và y có phải là anh em họ hay không.

Vì vậy, nếu đầu vào giống như

x =5, y =4, thì kết quả đầu ra sẽ là true

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một bản đồ ô
Xác định một hàng đợi q
chèn root vào q
um [x]:=um [y]:=null
while (không phải q trống), do -
- qSize:=kích thước của q
- while qSize> 0 then (giảm qSize đi 1), thực hiện -
  - cur:=phần tử đầu tiên của q
  - xóa phần tử khỏi q
  - nếu bên trái của curr là hiện tại, thì -
    - nếu um có giá trị bên trái của cur thì
      - um [giá trị bên trái của cur]:=cur
    - Nếu không
      - chèn bên trái của cur vào q
    - nếu um có giá trị bên phải của cur thì
      - um [value of right of cur]:=cur
    - Nếu không
      - chèn bên phải của cur vào q
  - nếu um [x] hoặc um [y] khác 0 thì -
    - nếu um [x] là 0 hoặc um [y] là 0 hoặc um [x] giống như um [y] thì -
      - trả về false
    - Nếu không
      - trả về true
trả về false

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

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

Đầu vào

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

Anh em họ trong Cây nhị phân trong C ++

Ví dụ

Đầu vào

Đầu ra