Postorder Traversal ของ Binary Tree โดยไม่ใช้ Recursion และ Stack ใน C++

ในปัญหานี้ เราได้รับ Binary Tree งานคือพิมพ์ Postorder Traversal โดย ไม่ใช้ Recursion และไม่ใช้ Stack

ความรู้พื้นฐาน

Binary Tree คือ ต้นไม้ที่แต่ละโหนดมีลูกได้สูงสุด 2 โหนด

Postorder Traversal คือ เดินซ้าย → เดินขวา → ไปที่ราก

Postorder traversal ของต้นไม้ตัวอย่าง: 8 4 2 7 9 6

วิธีที่ 1: ใช้ Hash Table (unordered_set) เก็บโหนดที่เยี่ยมชมแล้ว

ใช้ Depth-First Search และเก็บโหนดที่ผ่านมาใน unordered_set เพื่อไม่ให้วนซ้ำ

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

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

void postOrderTraversal(struct Node* head) {
    struct Node* temp = head;
    unordered_set<Node*> visited;
    
    while (temp && visited.find(temp) == visited.end()) {
        if (temp->left && visited.find(temp->left) == visited.end())
            temp = temp->left;
        else if (temp->right && visited.find(temp->right) == visited.end())
            temp = temp->right;
        else {
            cout << temp->data << "\t";
            visited.insert(temp);
            temp = head; // กลับไปที่รากเพื่อหาโหนดถัดไป
        }
    }
}

// ฟังก์ชันสร้างโหนดและ main() เหมือนเดิม...

วิธีที่ 2: ใช้ unordered_map เก็บ Parent Pointer (ดีกว่า)

แทนที่จะกลับไปที่รากทุกครั้ง ให้เก็บ parent ของแต่ละโหนดใน map เพื่อย้อนกลับได้โดยตรง

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

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

void postOrderTraversal(Node* root) {
    Node* n = root;
    unordered_map<Node*, Node*> postorder;
    postorder.insert(pair<Node*, Node*>(root, nullptr));
    
    while (n) {
        if (n->left && postorder.find(n->left) == postorder.end()) {
            postorder.insert(pair<Node*, Node*>(n->left, n));
            n = n->left;
        }
        else if (n->right && postorder.find(n->right) == postorder.end()) {
            postorder.insert(pair<Node*, Node*>(n->right, n));
            n = n->right;
        }
        else {
            cout << n->data << "\t";
            n = (postorder.find(n))->second; // ย้อนกลับไป parent
        }
    }
}

// ฟังก์ชันสร้างโหนดและ main() เหมือนเดิม...

ผลลัพธ์ (ทั้งสองวิธี)

Post Order Traversal of the binary tree : 8   4   2   13   7   9   6

สรุป

วิธีที่ 2 ดีกว่าเพราะไม่ต้อง reset กลับไปที่รากทุกครั้ง ลดเวลาการทำงานได้อย่างมาก