두 스택을 사용하는 반복적 인 사후 순회

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 팩트 셋 포카이트 Paytm
스택 나무조회수 21

문제 정책

“두 스택을 사용한 반복적 인 포스트 오더 순회”문제는 n 개의 노드가있는 이진 트리가 제공된다는 것을 나타냅니다. 두 개의 스택을 사용하여 반복적 인 postorder traversal을위한 프로그램을 작성하십시오.

두 스택을 사용하는 반복적 인 사후 순회핀

예

입력

두 스택을 사용하는 반복적 인 사후 순회핀

 

4 5 2 6 7 3 1

입력

핀

 

4 2 3 1

암호알고리즘

  1. 다음으로 구성된 노드에 대한 구조를 만듭니다. 정수 데이터 및 XNUMX 노드 유형 포인터를 왼쪽 및 오른쪽으로 유지하는 변수입니다.
  2. 그런 다음 정수 값을 매개 변수로 받아들이는 새 노드를 만드는 함수를 만듭니다. 그 안에 노드를 만듭니다. 매개 변수로 전달 된 정수 값을 데이터 변수에 저장하고 오른쪽 및 왼쪽 포인터 노드를 null로 업데이트합니다. 새로 생성 된 노드를 반환합니다.
  3. 마찬가지로, 반복을위한 함수를 만듭니다. 주문 후 순회 바이너리 트리의 루트 노드에 대한 포인터를받습니다. 루트 노드가 null인지 확인하고 반환합니다.
  4. 두 개 만들기 스택 순회에 도움이되는 Node * 유형의 데이터 구조.
  5. 스택에 루트 노드 푸시 / 삽입 1. 다른 새 노드를 만듭니다.
  6. 스택 1은 비어 있지 않지만 즉 스택 1의 크기는 0이 아닙니다. 새 노드의 스택 1의 맨 위에 노드를 저장하고 스택에서 팝 / 제거합니다. 제거 된 노드를 스택에 푸시 / 삽입 2. 현재 노드의 왼쪽이 있는지 확인하고 스택 1에 푸시 / 삽입합니다. 마찬가지로 노드의 오른쪽이 있는지 확인하고 스택 1에 푸시합니다.
  7. 스택 1이 비어 있지 않은 상태에서 다시 트래버스하고 두 번째 스택의 스택 1 맨 위에 노드를 저장하고 첫 번째 스택에서 팝합니다.
  8. 마지막으로 두 번째 노드를 인쇄합니다.

암호

두 스택을 사용하는 반복적 인 사후 순회를위한 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) n 개의 노드에 공간을 사용했기 때문입니다.

Translate »
1