พิมพ์เส้นทาง Root-to-Leaf ที่สั้นที่สุดและอยู่ซ้ายสุดใน Binary Tree ด้วย C++

กำหนด Binary Tree โปรแกรมต้องหาเส้นทางจากรากไปยังใบ (root-to-leaf) ที่สั้นที่สุดจากหลายเส้นทางที่มีอยู่

เนื่องจากเราท่องต้นไม้จากซ้ายไปขวา หากมีเส้นทางสั้นที่สุดหลายเส้นทาง โปรแกรมจะพิมพ์เส้นทางแรกที่ถูกท่องซึ่งเป็นเส้นทางสั้นที่สุดทางด้านซ้ายของต้นไม้

เราสามารถใช้คิว (queue) ที่จะท่องแต่ละระดับด้วย Level Order Traversal และเส้นทางที่มีจำนวนระดับน้อยที่สุดจะถูกพิมพ์ เนื่องจากมันจะเป็นเส้นทางสั้นที่สุดจากรากไปใบ

ในต้นไม้ข้างต้น เส้นทางจากรากไปใบหลายเส้นทางคือ:

10 -> 3 (เส้นทางสั้นที่สุด)
10 -> 211 -> 100
10 -> 211 -> 146

ตัวอย่าง

Input: 10 3 211 100 146
Output: 10 3

อัลกอริทึม

ขั้นตอนที่ 1: สร้างโครงสร้างโหนด
    struct node { struct node *left, *right; int data; }
ขั้นตอนที่ 2: ฟังก์ชันสร้างโหนด newnode(int data)
ขั้นตอนที่ 3: ฟังก์ชันคำนวณเส้นทาง path(int data, unordered_map<int,int> prnt)
ขั้นตอนที่ 4: ฟังก์ชันหาเส้นทางซ้าย left(Node* root)
    สร้าง queue<Node*> que
    que.push(root)
    int leaf = -1
    Node* temp = NULL
    unordered_map<int, int> prnt
    prnt[root->data] = root->data
    Loop while !que.empty()
        temp = que.front()
        que.pop()
        ถ้า !temp->left && !temp->right
            leaf = temp->data
            break
        ไม่เช่นนั้น
            ถ้า temp->left que.push, prnt[left] = temp
            ถ้า temp->right que.push, prnt[right] = temp
        จบถ้า
    จบลูป
    path(leaf, prnt)
    พิมพ์ leaf
ขั้นตอนที่ 5: ใน main() สร้างต้นไม้ เรียก left(root)

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

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

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

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

void path(int data, unordered_map<int, int> prnt) {
    if (prnt[data] == data)
        return;
    path(prnt[data], prnt);
    cout << prnt[data] << " ";
}

void left(Node* root) {
    queue<Node*> que;
    que.push(root);
    int leaf = -1;
    Node* temp = NULL;
    unordered_map<int, int> prnt;
    prnt[root->data] = root->data;
    while (!que.empty()) {
        temp = que.front();
        que.pop();
        if (!temp->left && !temp->right) {
            leaf = temp->data;
            break;
        } else {
            if (temp->left) {
                que.push(temp->left);
                prnt[temp->left->data] = temp->data;
            }
            if (temp->right) {
                que.push(temp->right);
                prnt[temp->right->data] = temp->data;
            }
        }
    }
    path(leaf, prnt);
    cout << leaf << " ";
}

int main() {
    Node* root = newnode(90);
    root->left = newnode(21);
    root->right = newnode(32);
    root->left->left = newnode(45);
    root->right->left = newnode(52);
    root->right->right = newnode(27);
    root->left->left->left = newnode(109);
    root->left->left->right = newnode(101);
    root->right->right->left = newnode(78);
    left(root);
    return 0;
}

ผลลัพธ์

90 32 52