การส่งผ่านหลังการสั่งซื้อซ้ำโดยใช้สองกอง


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อะโดบี อเมซอน ข้อเท็จจริง โฟร์ไคต์ Paytm
กอง ต้นไม้

คำชี้แจงปัญหา

ปัญหา“ การข้ามผ่านหลังการสั่งซื้อซ้ำโดยใช้สองกอง” ระบุว่าคุณได้รับต้นไม้ไบนารีที่มีโหนด เขียนโปรแกรมสำหรับการส่งผ่านหลังการสั่งซื้อซ้ำโดยใช้สองกอง

การส่งผ่านหลังการสั่งซื้อซ้ำโดยใช้สองกอง

ตัวอย่าง

อินพุต

การส่งผ่านหลังการสั่งซื้อซ้ำโดยใช้สองกอง

 

4 5 2 6 7 3 1

อินพุต

 

4 2 3 1

ขั้นตอนวิธี

  1. สร้างโครงสร้างสำหรับโหนดที่ประกอบด้วยไฟล์ จำนวนเต็ม ตัวแปรเพื่อเก็บข้อมูลและตัวชี้ประเภทสองโหนดไปทางซ้ายและขวา
  2. หลังจากนั้นให้สร้างฟังก์ชันเพื่อสร้างโหนดใหม่ซึ่งรับค่าจำนวนเต็มเป็นพารามิเตอร์ สร้างโหนดภายใน จัดเก็บค่าจำนวนเต็มที่ส่งผ่านเป็นพารามิเตอร์ในตัวแปรข้อมูลและอัปเดตโหนดตัวชี้ด้านขวาและด้านซ้ายเป็น null ส่งคืนโหนดที่สร้างขึ้นใหม่
  3. ในทำนองเดียวกันให้สร้างฟังก์ชันสำหรับการวนซ้ำ โพสต์การส่งผ่านคำสั่งซื้อ ซึ่งรับตัวชี้ไปยังโหนดรากของต้นไม้ไบนารี ตรวจสอบว่าโหนดรูทเท่ากับ null หรือไม่ให้ส่งคืน
  4. สร้างสอง กอง โครงสร้างข้อมูลประเภท Node * เพื่อช่วยในการส่งผ่าน
  5. พุช / แทรกโหนดรูทในสแต็ก 1. สร้างโหนดใหม่ขึ้นมา
  6. ในขณะที่สแต็ก 1 ไม่ว่างนั่นคือขนาดของสแต็ก 1 ไม่เท่ากับ 0 เก็บโหนดที่ด้านบนสุดของสแต็ก 1 ในโหนดใหม่และป๊อป / ลบออกจากสแต็ก ดัน / แทรกโหนดที่ถอดออกในสแต็ก 2. ตรวจสอบว่ามีโหนดทางซ้ายของโหนดปัจจุบันอยู่หรือไม่ดัน / แทรกในสแต็ก 1 ในทำนองเดียวกันตรวจสอบว่ามีโหนดอยู่ทางขวาหรือไม่ดันในสแต็ก 1
  7. สำรวจอีกครั้งในขณะที่สแต็ก 1 ไม่ว่างให้เก็บโหนดที่ด้านบนสุดของสแต็ก 1 ในสแต็กที่ 2 และนำมาจากสแตกที่ 1
  8. ในที่สุดพิมพ์โหนดที่ 2

รหัส

โปรแกรม C ++ สำหรับการข้ามผ่านหลังการสั่งซื้อซ้ำโดยใช้สองกอง

#include <bits/stdc++.h> 
using namespace std; 
  
struct Node{ 
    int data; 
    Node *left, *right; 
}; 
  
Node* newNode(int data){ 
    Node* node = new Node; 
    node->data = data; 
    node->left = node->right = NULL; 
    return node; 
} 

void postOrderIterative(Node* root){ 
    if(root == NULL){ 
        return; 
    }
  
    stack<Node *> s1, s2; 
  
    s1.push(root); 
    Node* node; 
  
    while(!s1.empty()){ 
        node = s1.top(); 
        s1.pop(); 
        s2.push(node); 
  
        if(node->left){ 
            s1.push(node->left);
        }
        if(node->right){ 
            s1.push(node->right);
        }
    } 
  
    while(!s2.empty()){ 
        node = s2.top(); 
        s2.pop(); 
        cout << node->data << " "; 
    } 
} 
  
int main(){ 
    Node* root = NULL; 
    root = newNode(1); 
    root->left = newNode(2); 
    root->right = newNode(3); 
    root->left->left = newNode(4); 
    root->left->right = newNode(5); 
    root->right->left = newNode(6); 
    root->right->right = newNode(7); 
  
    postOrderIterative(root); 
  
    return 0; 
}
4 5 2 6 7 3 1

โปรแกรม Java สำหรับการข้ามผ่านหลังการสั่งซื้อซ้ำโดยใช้สองกอง

import java.util.*; 

class IterativePostorder{ 
  
    static class node{ 
        int data; 
        node left, right; 
  
        public node(int data){ 
            this.data = data; 
        } 
    } 
  
    static Stack<node> s1, s2; 
  
    static void postOrderIterative(node root){ 
        s1 = new Stack<>(); 
        s2 = new Stack<>(); 
  
        if(root == null){ 
            return; 
        }
  
        s1.push(root); 
  
        while(!s1.isEmpty()){ 
            node temp = s1.pop(); 
            s2.push(temp); 
  
            if(temp.left != null){ 
                s1.push(temp.left);
            }
            
            if(temp.right != null){ 
                s1.push(temp.right);
            }
        } 
  
        while(!s2.isEmpty()){ 
            node temp = s2.pop(); 
            System.out.print(temp.data + " "); 
        } 
    } 
  
    public static void main(String[] args){ 
        
        node root = null; 
        root = new node(1); 
        root.left = new node(2); 
        root.right = new node(3); 
        root.left.left = new node(4); 
        root.left.right = new node(5); 
        root.right.left = new node(6); 
        root.right.right = new node(7); 
  
        postOrderIterative(root); 
    } 
}
4 5 2 6 7 3 1

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา

O (n) โดยที่ n คือจำนวนโหนดที่แทรก

ความซับซ้อนของอวกาศ

O (n) เพราะเราใช้พื้นที่สำหรับโหนด