Nút anh em ruột trong cây nhị phân C++

Giới thiệu

Cho một cây nhị phân, gốc ở độ sâu 0. Hai nút được gọi là anh em ruột (cousins) nếu chúng ở cùng độ sâu nhưng có cha khác nhau. Kiểm tra xem hai nút có giá trị x và y có phải anh em ruột hay không.

Ví dụ

Cây: root=1, left=2, right=3, 2->right=4, 3->right=5. Với x=5, y=4 → Kết quả: true (cùng độ sâu 2, cha khác nhau).

Ý tưởng giải thuật (BFS theo cấp độ)

1. Sử dụng hàng đợi để duyệt BFS theo từng cấp độ (level).
2. Dùng unordered_map parent lưu cha của mỗi nút giá trị x và y.
3. Tại mỗi cấp độ, duyệt tất cả nút trong hàng đợi:
   • Nếu con trái/phải có giá trị x hoặc y, lưu cha vào map.
   • Nếu không phải x/y, đưa vào hàng đợi để xử lý cấp độ sau.
4. Sau khi xử lý xong một cấp độ, kiểm tra:
   • Nếu cả x và y đều tìm thấy cha → so sánh cha. Khác nhau → true, cùng cha → false.
   • Nếu chỉ một trong hai tìm thấy → false (khác độ sâu).

Ví dụ triển khai (C++)

#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*> parent;
        queue<TreeNode*> q;
        q.push(root);
        parent[x] = parent[y] = nullptr;
        
        while (!q.empty()) {
            int sz = q.size();
            while (sz--) {
                TreeNode* cur = q.front(); q.pop();
                if (cur->left) {
                    if (parent.count(cur->left->val))
                        parent[cur->left->val] = cur;
                    else
                        q.push(cur->left);
                }
                if (cur->right) {
                    if (parent.count(cur->right->val))
                        parent[cur->right->val] = cur;
                    else
                        q.push(cur->right);
                }
            }
            if (parent[x] || parent[y]) {
                if (!parent[x] || !parent[y] || parent[x] == parent[y])
                    return false;
                return true;
            }
        }
        return false;
    }
};

int 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); // 1 (true)
    return 0;
}

Đầ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); ob.isCousins(root, 5, 4)

Đầu ra

1