หาโหนดที่ N ใน Postorder Traversal ของ Binary Tree ด้วย C++

ภาพรวมปัญหา

ได้รับ Binary Tree และ N หาโหนดที่ N ใน Postorder Traversal (Left, Right, Root)

ตัวอย่าง

อินพุต

N = 6

เอาต์พุต

3

คำอธิบาย

Postorder: 4, 5, 2, 6, 7, 3, 1
ตัวที่ 6 = 3

วิธีแก้ปัญหา

Postorder Traversal แบบ Recursive: Left → Right → Root

หมายเหตุ: โค้ดต้นฉบับมีข้อผิดพลาดร้ายแรง (โค้ดคำนวณ Fortunate Number ไม่เกี่ยวข้อง) เขียนใหม่ให้ถูกต้อง

โค้ดตัวอย่าง (แก้ไขแล้ว)

#include <iostream>
using namespace std;

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

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

void findPostOrderTraversalRec(Node* root, int N) {
    static int nodeCount = 0;
    if (root == NULL) return;
    if (nodeCount <= N) {
        findPostOrderTraversalRec(root->left, N);
        findPostOrderTraversalRec(root->right, N);
        nodeCount++;
        if (nodeCount == N)
            cout << root->data;
    }
}

int main() {
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    
    int N = 6;
    cout << N << "th node in postorder traversal is ";
    findPostOrderTraversalRec(root, N);
    return 0;
}

เอาต์พุต

6th node in postorder traversal is 3

สรุป

Postorder: Left → Right → Root นับหลังจากเยี่ยมลูกทั้งสองข้างแล้ว