พิมพ์ลูกพี่ลูกน้อง (Cousins) ของโหนดใน Binary Tree ใน C++

โจทย์

ให้ Binary Tree และโหนดเป้าหมาย ต้องการหาโหนดลูกพี่ลูกน้อง (Cousins) คือโหนดที่อยู่ระดับเดียวกัน (Same Level) แต่มี Parent ต่างกัน

วิธีแก้ปัญหา

1. หา Level ของโหนดเป้าหมาย

พิมพ์โหนดทั้งหมดใน Level นั้น ยกเว้น:

• โหนดเป้าหมายเอง
• Siblings (โหนดที่มี Parent เหมือนกัน)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

struct Node { int data; Node *left, *right; };
Node* newNode(int item) {
    Node* temp = new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}

int levelOfNode(Node* root, Node* node, int level) {
    if (root == NULL) return 0;
    if (root == node) return level;
    int downlevel = levelOfNode(root->left, node, level + 1);
    if (downlevel != 0) return downlevel;
    return levelOfNode(root->right, node, level + 1);
}

void printCousin(Node* root, Node* node, int level) {
    if (root == NULL || level < 2) return;
    if (level == 2) {
        if (root->left == node || root->right == node) return;
        if (root->left) cout << root->left->data << " ";
        if (root->right) cout << root->right->data;
    } else if (level > 2) {
        printCousin(root->left, node, level - 1);
        printCousin(root->right, node, level - 1);
    }
}

void cousinNode(Node* root, Node* node) {
    int level = levelOfNode(root, node, 1);
    printCousin(root, node, level);
}

int main() {
    Node* root = newNode(11);
    root->left = newNode(15);
    root->right = newNode(4);
    root->left->left = newNode(3);
    root->left->right = newNode(7);
    root->left->right->right = newNode(9);
    root->right->left = newNode(17);
    root->right->right = newNode(8);
    root->right->left->right = newNode(5);
    cout << "The cousin nodes are: \t";
    cousinNode(root, root->right->right);
    return 0;
}

ผลลัพธ์

The cousin nodes are: 3 7