In Tất Cả Nút Lá Của Cây Nhị Phân Từ Trái Sang Phải Bằng Cách Lặp Trong C++

Trong bài toán này, chúng ta được cho một cây nhị phân và phải in tất cả nút lá của cây từ trái sang phải bằng cách lặp (iterative).

Ví dụ để hiểu vấn đề:

Đầu vào:

Đầu ra – 1 4 7

Để giải quyết bằng cách lặp, ta sử dụng DFS (tìm kiếm theo chiều sâu). Duyệt cây bắt đầu từ gốc, kiểm tra nếu là nút lá thì in, ngược lại tìm cây con và duyệt đệ quy để tìm tất cả nút lá.

Ví Dụ

Mã triển khai giải pháp:

#include <iostream>
using namespace std;

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

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

void printLTRLeafNodes(Node* root) {
    if (!root) return;
    if (!root->left && !root->right) {
        cout << root->data << "\t";
        return;
    }
    if (root->left)
        printLTRLeafNodes(root->left);
    if (root->right)
        printLTRLeafNodes(root->right);
}

int main() {
    Node* root = insertNode(21);
    root->left = insertNode(5);
    root->right = insertNode(36);
    root->left->left = insertNode(2);
    root->right->left = insertNode(13);
    root->right->right = insertNode(4);
    root->right->left->left = insertNode(76);
    root->right->left->right = insertNode(9);
    root->right->right->left = insertNode(17);
    root->right->right->right = insertNode(2);
    cout << "Các nút lá của cây từ trái sang phải là:\n";
    printLTRLeafNodes(root);
    return 0;
}

Đầu Ra

Các nút lá của cây từ trái sang phải là: 2 76 9 17 2