재귀없이 주어진 이진 트리 노드의 조상 인쇄


난이도 중급
자주 묻는 질문 수행자 아마존 포카이트
스택 나무 트리 순회

이진 트리와 특정 노드 또는 키가 주어집니다. 주어진 조상 인쇄 이진 트리 재귀없는 노드.

재귀없이 주어진 이진 트리 노드의 조상 인쇄

입력 :

키 = 7

재귀없이 주어진 이진 트리 노드의 조상 인쇄

출력 : 3 1

입력 :

키 = 4

재귀없이 주어진 이진 트리 노드의 조상 인쇄

출력 : 2 1

주어진 이진 트리 노드의 조상을위한 알고리즘

  1. 데이터를 보유 할 정수 변수와 왼쪽과 오른쪽 두 개의 Node 유형 객체를 포함하는 클래스 Node를 만듭니다. 정수 값을 매개 변수로 받아들이는 매개 변수화 된 생성자를 내부에 만들고 클래스 노드의 정수 변수에 저장합니다.
  2. 그런 다음 트리의 루트 노드와 키를 매개 변수로 받아들이는 주어진 키의 조상을 인쇄하는 함수를 만듭니다.
  3. 루트가 null인지 확인하고 반환합니다. 그렇지 않으면 노드 유형의 스택 데이터 구조를 만듭니다.
  4. 주어진 바이너리 탐색 시작 나무.
  5. 루트가 null과 같지 않고 루트의 데이터가 주어진 키와 같지 않은 동안 스택에서 루트를 푸시하고 루트를 루트의 왼쪽으로 업데이트합니다.
  6. 루트가 null이 아니고 루트의 데이터가 주어진 키와 같으면 루프를 중단하십시오.
  7. 그렇지 않으면 스택 맨 위에있는 노드의 오른쪽이 null과 같으면 스택 맨 위에있는 노드에서 루트를 업데이트하고 스택 맨 위에 팝니다. 스택이 비어 있지 않고 스택 맨 위에있는 노드의 오른쪽이 루트와 같지만 스택 맨 위에있는 노드에서 루트를 업데이트하고 스택.
  8. 스택이 비어있는 경우 루트를 null로 업데이트하고 그렇지 않으면 루트를 스택 맨 위에있는 노드의 오른쪽으로 업데이트합니다.
  9. 스택이 비어 있지 않은 동안 스택 상단에 노드의 데이터를 인쇄하고 스택 상단을 팝합니다.

주어진 이진 트리 노드의 조상을위한 C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 
  
struct Node{ 
    int data; 
    struct Node *left, *right; 
}; 
  
struct Node* newNode(int data){ 
    struct Node* node = (struct Node*) malloc(sizeof(struct Node)); 
    node->data = data; 
    node->left = node->right = NULL; 
    return node; 
} 
  
void printAncestors(struct Node *root, int key){ 
    if(root == NULL){ 
        return; 
    }
  
    stack<struct Node* > st; 
  
    while(1){ 
        while(root && root->data != key){ 
            st.push(root);  
            root = root->left;
        } 
  
        if(root && root->data == key){ 
            break; 
        }
  
        if(st.top()->right == NULL){ 
            root = st.top(); 
            st.pop(); 
  
            while(!st.empty() && st.top()->right == root){ 
               root = st.top(); 
               st.pop(); 
            } 
        } 
  
        root = st.empty()? NULL: st.top()->right; 
    } 
  
    while(!st.empty()){ 
        cout<<st.top()->data<<" "; 
        st.pop(); 
    } 
} 
  
int main(){ 
    
    struct Node* 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); 
    
    int key = 7;
    
    printAncestors(root, key); 
  
    return 0; 
}
3 1

주어진 이진 트리 노드의 조상을위한 자바 프로그램

import java.util.Stack; 
  
class findAncestors{ 
    
    static class Node{ 
        int data; 
        Node left,right; 
          
        Node(int data){ 
            this.data = data; 
        } 
    } 
      
    static void printAncestors(Node root,int key){ 
        if(root == null){ 
            return; 
        }
          
        Stack<Node> st = new Stack<>(); 
          
        while(true){ 
              
            while(root != null && root.data != key){ 
                st.push(root);   
                root = root.left;
            } 
              
            if(root != null && root.data == key){ 
                break; 
            }
              
            if(st.peek().right == null){ 
                root =st.peek(); 
                st.pop(); 
                  
                while( st.empty() == false && st.peek().right == root){ 
                    root = st.peek(); 
                    st.pop(); 
                } 
            } 
              
            root = st.empty() ? null : st.peek().right; 
        } 
          
        while(!st.empty()){ 
            System.out.print(st.peek().data+" "); 
            st.pop(); 
        } 
    } 
      
    public static void main(String[] args){ 
         
        Node 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); 
        
        int key = 7;
        
        printAncestors(root, key); 
    } 
  
}
3 1

복잡성 분석

시간 복잡성 : O (n) 여기서 n은 삽입 된 노드의 수입니다.

공간 복잡성 : O (n)은 n 개의 노드에 공간을 사용했기 때문입니다.

참조