พิมพ์โหนดระหว่างสองระดับใน Binary Tree ใน C++

ภาพรวมปัญหา

ได้รับ Binary Tree และสองระดับ (upper, lower) ต้องพิมพ์โหนดระหว่างระดับเหล่านั้น

ตัวอย่าง

Upper = 1, Lower = 3

Output: 6 3 9 7 4 8 10

วิธีแก้ปัญหา (Level Order Traversal with Queue)

1. ใช้ Queue ทำ Level Order Traversal
2. ใช้ Marker แยกระดับ
3. พิมพ์เฉพาะระดับที่อยู่ระหว่าง lower ถึง upper

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

#include <iostream>
#include <queue>
using namespace std;

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

void printNodesAtLevel(Node* root, int low, int high) {
    queue<Node*> Q;
    Node* marker = new Node;
    int level = 1;
    Q.push(root);
    Q.push(marker);
    while (!Q.empty()) {
        Node* n = Q.front(); Q.pop();
        if (n == marker) {
            cout << endl;
            level++;
            if (Q.empty() || level > high) break;
            Q.push(marker);
            continue;
        }
        if (level >= low) cout << n->key << " ";
        if (n->left) Q.push(n->left);
        if (n->right) Q.push(n->right);
    }
}

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

int main() {
    struct Node* root = insertNode(6);
    root->left = insertNode(3);
    root->right = insertNode(9);
    root->left->left = insertNode(7);
    root->left->right = insertNode(4);
    root->left->right->left = insertNode(8);
    root->left->right->right = insertNode(10);
    root->left->right->right->left = insertNode(5);
    root->left->right->right->right = insertNode(1);
    root->left->right->left->left = insertNode(14);
    root->left->right->left->right = insertNode(26);
    int upper = 3, lower = 1;
    cout << "Level wise Nodes between level " << lower << " and " << upper << " are:\n";
    printNodesAtLevel(root, lower, upper);
    return 0;
}

ผลลัพธ์ (Output)

Level wise Nodes between level 1 and 3 are:
6 3 9 7 4