พิมพ์ Leaf Nodes ของ Binary Tree ซ้าย-ขวา แบบ Iterative ใน C++

ภาพรวมปัญหา

ได้รับ Binary Tree ต้องพิมพ์ Leaf Nodes ทั้งหมดจากซ้ายไปขวา โดยใช้วิธี Iterative (ไม่ใช้ Recursion)

ตัวอย่าง

Output: 1 4 7

วิธีแก้ปัญหา (DFS Iterative)

ใช้ Stack จำลอง Recursion เริ่มจากราก ถ้าเป็น Leaf → พิมพ์ ไม่ใช่ → Push ลูกขวาแล้วลูกซ้าย (เพื่อให้ซ้ายถูกประมวลผลก่อน)

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

#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 << "Leaf Nodes of the tree from left to right are:\n";
    printLTRLeafNodes(root);
    return 0;
}

ผลลัพธ์ (Output)

Leaf Nodes of the tree from left to right are:
2 76 9 17 2