หาการทะลุ Postorder ของ BST จาก Preorder traversal ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ preOrder[] ที่แทนการทะลุ preorder ของ binary search tree งานของเราคือ หาการทะลุ postorder ของ BST จาก preorder traversal

มาดูตัวอย่างเพื่อเข้าใจปัญหา

Input

preOrder[] = {5, 2, 4, 7, 12}

Output

{4, 2, 12, 7, 5}

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

วิธีแก้ที่ง่ายคือสร้าง BST จาก preorder traversal ที่กำหนด แล้วทำ postorder traversal ของต้นไม้ วิธีนี้โอเค แต่มีวิธีที่มีประสิทธิภาพมากกว่า

เราจะทะลุอาร์เรย์ preorder พร้อมขีดจำกัดค่าเพื่อแยกค่าของ subtree ซ้ายและขวา

ลำดับการทะลุคือ

preOrder: Root -> Left -> Right 
postOrder: Left -> Right -> Root

สำหรับองค์ประกอบแรกใน preorder ซึ่งเป็นราก ขีดจำกัดคือ {INT_MIN, Root} จากนั้นทะลุอาร์เรย์ preorder และสลับองค์ประกอบทั้งหมดในขีดจำกัดกับค่าสุดท้ายของขีดจำกัด คล้ายกัน เราจะทำซ้ำสำหรับ subtree ขวา และเพิ่มรากท้ายสุด

โปรแกรมแสดงการทำงานของวิธีแก้ (Recursive)

ตัวอย่าง

#include <iostream> 
using namespace std; 

void findPostOrderTraversalRec(int pre[], int n, int lowerLimit, int upperLimit, int& index){ 
    if (index == n) 
        return; 
    if (pre[index] < lowerLimit || pre[index] > upperLimit) 
        return; 
    int currNode = pre[index]; 
    index++; 
    findPostOrderTraversalRec(pre, n, lowerLimit, currNode, index); 
    findPostOrderTraversalRec(pre, n, currNode, upperLimit, index); 
    cout<<currNode<<" "; 
} 

void findPostOrderTraversalFromPreOrder(int pre[], int n){ 
    int index = 0; 
    findPostOrderTraversalRec(pre, n, -1000, 1000, index); 
} 

int main(){ 
    int pre[] = { 5, 2, 4, 7, 12 }; 
    int n = sizeof(pre) / sizeof(pre[0]); 
    cout<<"PreOrder Traversal: \t"; 
    for(int i = 0; i < n ; i++) 
        cout<<pre[i]<<" "; 
    cout<<endl<<"Post Order Traversal: \t"; 
    findPostOrderTraversalFromPreOrder(pre, n); 
    return 0; 
}

ผลลัพธ์

PreOrder Traversal: 5 2 4 7 12 
Post Order Traversal: 4 2 12 7 5

อีกวิธีหนึ่งคือใช้ iteration เนื่องจากเรารู้ว่า preorder คือ root -> left -> right และ postOrder คือ left -> right -> root สิ่งนี้สามารถคำนวณได้โดยใช้ลูปและคำนวณ pivot element ซึ่งคือจุดที่องค์ประกอบสุดท้ายของ left element อยู่ โดยใช้ pivot เราจะพิมพ์ left ก่อน แล้ว right แล้ว root

Pivot หาได้โดยหาดัชนีขององค์ประกอบที่มากกว่ารากแรก

โปรแกรมแสดงการทำงานของวิธีแก้ (Iterative)

ตัวอย่าง

#include <iostream> 
using namespace std; 

void findPostOrderTraversalFromPreOrder(int pre[], int n){ 
    int pivot = 0; 
    for(int i = 1; i < n; i++){ 
        if (pre[0] <= pre[i]) { 
            pivot = i; 
            break; 
        } 
    } 
    for(int i = pivot - 1; i > 0; i--){ 
        cout << pre[i] << " "; 
    } 
    for(int i = n - 1; i >= pivot; i--) { 
        cout << pre[i] << " "; 
    } 
    cout << pre[0]; 
} 

int main(){ 
    int pre[] = { 5, 2, 4, 7, 12 }; 
    int n = sizeof(pre) / sizeof(pre[0]); 
    cout<<"PreOrder Traversal: \t"; 
    for(int i = 0; i < n ; i++) 
        cout<<pre[i]<<" "; 
    cout<<endl<<"Post Order Traversal: \t"; 
    findPostOrderTraversalFromPreOrder(pre, n); 
    return 0; 
}

ผลลัพธ์

PreOrder Traversal: 5 2 4 7 12 
Post Order Traversal: 4 2 12 7 5