พิมพ์เส้นทางระหว่างโหนดสองตัวใน Binary Tree ด้วย C++

เราได้รับ Binary Tree ที่มีโหนดต่างกันทั้งหมด และมีโหนดสองตัวที่ต้องการพิมพ์เส้นทางระหว่างกันใน Binary Tree

ตัวอย่าง - ต้องการพิมพ์เส้นทางจากโหนด 140 ไป 211 ผลลัพธ์ควรเป็น:

Output: 140->3->10->211

แนวคิดคือหาเส้นทางจากโหนดราก (root) ไปยังโหนดทั้งสอง และเก็บไว้ในสองเวกเตอร์/อาร์เรย์ คือ path1 และ path2

จะมี 2 กรณีเกิดขึ้น:

• ถ้าสองโหนดอยู่ใน subtree ต่างกันของราก - เมื่อหนึ่งอยู่ซ้าย อีกอันขวา รากจะอยู่กลางเส้นทางระหว่าง node1 และ node2 พิมพ์ path1 ย้อนกลับ แล้วตามด้วย path2

• ถ้าทั้งสองโหนดอยู่ใน subtree เดียวกัน - ทั้งคู่อยู่ซ้ายหรือขวา เส้นทางจากรากไปทั้งสองโหนดจะมีจุดตัด (intersection) ก่อนที่เส้นทางจะแบ่ง เราต้องหาจุดตัดและพิมพ์โหนดจากจุดนั้นแบบกรณีแรก

อัลกอริทึม

START
ขั้นตอนที่ 1: กำหนด struct Node พร้อม int data และ Node *left, *right
ขั้นตอนที่ 2: ฟังก์ชัน tree(int data) สร้างโหนดต้นไม้
ฟังก์ชัน bool path(Node* root, vector& arr, int x)
    ขั้นตอนที่ 1: ถ้า root เป็น NULL RETURN false
    ขั้นตอนที่ 2: arr.push_back(root->data)
        ถ้า root->data == x RETURN true
    ขั้นตอนที่ 3: ถ้า path(root->left, arr, x) || path(root->right, arr, x) RETURN true
    ขั้นตอนที่ 4: arr.pop_back() RETURN false
END FUNCTION
ฟังก์ชัน void printPath(Node* root, int n1, int n2)
    ขั้นตอนที่ 1: กำหนด vector<int> path1
    ขั้นตอนที่ 2: กำหนด vector<int> path2
    ขั้นตอนที่ 3: เรียก path(root, path1, n1)
    ขั้นตอนที่ 4: เรียก path(root, path2, n2)
    ขั้นตอนที่ 5: กำหนด intersection = -1, i = 0, j = 0
    ขั้นตอนที่ 6: วนลูป while i != path1.size() || j != path2.size()
        ถ้า i == j && path1[i] == path2[j] เพิ่ม i, j
        ไม่เช่นนั้น intersection = j - 1, break
    END WHILE
    ขั้นตอนที่ 7: วนลูป for i = path1.size()-1 ถึง intersection+1 พิมพ์ path1[i]
    ขั้นตอนที่ 8: วนลูป for i = intersection ถึง path2.size()-1 พิมพ์ path2[i]
END FUNCTION

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

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

struct Node {
    int data;
    Node *left, *right;
};

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

bool path(Node* root, vector<int>& arr, int x) {
    if (!root)
        return false;
    arr.push_back(root->data);
    if (root->data == x)
        return true;
    if (path(root->left, arr, x) || path(root->right, arr, x))
        return true;
    arr.pop_back();
    return false;
}

void printPath(Node* root, int n1, int n2) {
    vector<int> path1;
    vector<int> path2;
    path(root, path1, n1);
    path(root, path2, n2);
    int intersection = -1;
    int i = 0, j = 0;
    while (i != path1.size() || j != path2.size()) {
        if (i == j && path1[i] == path2[j]) {
            i++;
            j++;
        } else {
            intersection = j - 1;
            break;
        }
    }
    for (int i = path1.size() - 1; i > intersection; i--)
        cout << path1[i] << " ";
    for (int i = intersection; i < path2.size(); i++)
        cout << path2[i] << " ";
}

int main() {
    struct Node* root = tree(1);
    root->left = tree(2);
    root->left->left = tree(4);
    root->left->left->left = tree(6);
    root->left->right = tree(5);
    root->left->right->left = tree(7);
    root->left->right->right = tree(8);
    root->right = tree(3);
    root->right->left = tree(9);
    root->right->right = tree(10);
    int node1 = 5;
    int node2 = 9;
    printPath(root, node1, node2);
    return 0;
}

ผลลัพธ์

5 2 1 3 9