Chương trình C++ in đường đi gốc đến lá ngắn nhất đầu tiên trong cây nhị phân

In đường đi từ gốc đến lá ngắn nhất đầu tiên trong cây nhị phân. Cây có giá trị phân biệt, tìm đường ngắn nhất từ gốc đến lá.

Dùng queue duyệt theo mức (level order) lưu các nút trên đường ngắn nhất. Khi đến nút lá trái nhất ở mức cuối, lấy giá trị từ queue in đường đi.

Ví dụ mã nguồn

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

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

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

void print_spath(int Data, unordered_map<int, int> parent) {
    if (parent[Data] == Data)
        return;
    print_spath(parent[Data], parent);
    cout << parent[Data] << " ";
}

void leftmost_path(struct Node* root) {
    queue<struct Node*> q;
    q.push(root);
    int LeafData = -1;
    struct Node* temp = NULL;
    unordered_map<int, int> parent;
    parent[root->data] = root->data;
    while (!q.empty()) {
        temp = q.front();
        q.pop();
        if (!temp->left && !temp->right) {
            LeafData = temp->data;
            break;
        } else {
            if (temp->left) {
                q.push(temp->left);
                parent[temp->left->data] = temp->data;
            }
            if (temp->right) {
                q.push(temp->right);
                parent[temp->right->data] = temp->data;
            }
        }
    }
    print_spath(LeafData, parent);
    cout << LeafData << " ";
}

int main() {
    struct Node* root = create_node(21);
    root->left = create_node(24);
    root->right = create_node(35);
    root->left->left = create_node(44);
    root->right->left = create_node(53);
    root->right->right = create_node(71);
    root->left->left->left = create_node(110);
    root->left->left->right = create_node(91);
    root->right->right->left = create_node(85);
    leftmost_path(root);
    return 0;
}

Kết quả đầu ra

21 35 53