พิมพ์บรรพบุรุษของโหนดใน Binary Tree แบบ Recursive ใน C++

โจทย์

ให้ Binary Tree และโหนดเป้าหมาย ต้องการพิมพ์บรรพบุรุษของโหนดนั้นแบบ Recursive

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

ใช้การท่องแบบ Recursive จาก Root ไปยังโหนดเป้าหมาย:

1. ถ้า Root เป็น NULL → คืนค่า false
2. ถ้า Root คือโหนดเป้าหมาย → คืนค่า true
3. เรียก Recursive ซ้ายและขวา ถ้าหนึ่งในสองคืน true → พิมพ์ค่า Root และคืน true
4. มิฉะนั้นคืนค่า false

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

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

struct node {
    int data;
    struct node* left;
    struct node* right;
};

bool AncestorsNodes(struct node *root, int target) {
    if (root == NULL) return false;
    if (root->data == target) return true;
    if (AncestorsNodes(root->left, target) || AncestorsNodes(root->right, target)) {
        cout << root->data << " ";
        return true;
    }
    return false;
}

struct node* insertNode(int data) {
    struct node* node = (struct node*) malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    struct node *root = insertNode(10);
    root->left = insertNode(6);
    root->right = insertNode(13);
    root->left->left = insertNode(3);
    root->left->right = insertNode(8);
    root->right->left = insertNode(12);
    cout << "Ancestor Nodes are ";
    AncestorsNodes(root, 8);
    getchar();
    return 0;
}

ผลลัพธ์

Ancestor Nodes are 6 10