ตรวจสอบคู่ในเส้นทางรูทถึงใบที่ผลรวมเท่ากับค่ารูทใน C++

โจทย์

ได้รับ Binary Tree ทางเราต้อง ตรวจสอบว่ามีคู่โหนดในเส้นทางจากรูทถึงใบ (Root-to-leaf path) ที่ผลรวมเท่ากับค่าของรูทหรือไม่

ตัวอย่าง

Input: ต้นไม้ดังภาพ (รูท=7, มีคู่ (2,5) และ (1,6))

Output: Yes

แนวทางแก้ปัญหา

ใช้ DFS พร้อม Hash Set:

1. ท่องต้นไม้จากรูทลงไป
2. เก็บค่าของโหนดที่ผ่านมาใน Hash Set
3. ที่โหนดใหม่ ตรวจสอบว่า rootVal - nodeVal อยู่ใน Hash Set หรือไม่
4. ถ้าพบ -> คืนค่า true, ถ้าจบไม่พบ -> false

โปรแกรมตัวอย่าง

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

struct Node { int data; struct Node* left, *right; };
struct Node* newnode(int data) {
    struct Node* node = new Node; node->data = data; node->left = node->right = NULL; return node;
}

bool findSumUntill(Node* node, unordered_set<int>& hashTable, int rootVal) {
    if (node == NULL) return false;
    int otherVal = rootVal - node->data;
    if (hashTable.find(otherVal) != hashTable.end()) return true;
    hashTable.insert(node->data);
    bool isFound = findSumUntill(node->left, hashTable, rootVal) || findSumUntill(node->right, hashTable, rootVal);
    hashTable.erase(node->data);
    return isFound;
}

bool findPairSum(Node* root) {
    unordered_set<int> hashTable;
    return findSumUntill(root->left, hashTable, root->data) || findSumUntill(root->right, hashTable, root->data);
}

int main() {
    struct Node* root = newnode(7);
    root->left = newnode(2); root->right = newnode(3);
    root->left->left = newnode(5); root->left->right = newnode(9);
    root->left->left->left = newnode(1); root->left->left->right = newnode(6);
    root->right->left = newnode(8);
    if (findPairSum(root)) cout << "Pair with sum equal to root value found";
    else cout << "No pairs found";
    return 0;
}

ผลลัพธ์

Pair with sum equal to root value found