주어진 이진 트리의 조상을 찾는 반복적 인 방법

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 포카이트 구글 인포에지 모건 스탠리 (Morgan Stanley) Paytm 삼성
스택 나무조회수 41

문제 정책

“주어진 조상을 찾는 반복적 인 방법 이진 트리”문제는 이진 트리와 키를 나타내는 정수가 주어 졌다는 것을 나타냅니다. 반복을 사용하여 주어진 키의 모든 조상을 인쇄하는 함수를 만듭니다.

주어진 이진 트리의 조상을 찾는 반복적 인 방법

입력 

주어진 이진 트리의 조상을 찾는 반복적 인 방법

키 = 6

5 2 1

설명 : 루트에서 값이 6 인 노드까지의 경로는 1 2 5 6입니다. 따라서 6에서 루트까지의 상위 시퀀스는 5 2 1입니다.

입력 :

주어진 이진 트리의 조상을 찾는 반복적 인 방법

키 = 10

9 7 1

암호알고리즘

1. Create a structure Node which contains an integer variable to hold data and two pointers left and right of type Node.
2. After that, create the parameterized constructor of the structure which accepts an integer value as it's parameter. Store the integer value in the data variable of Node and initialize left and right pointers as null.
3. Create a function to print the tree path which accepts an unordered map and an integer variable key as it's a parameter. While the key variable is equal to the map[key], print the key.
4. Similarly, create another function to set the parents for all the nodes in the given binary tree which accepts a pointer to the root node and an unordered map as it's parameter.
5. Create a stack data structure of Node* type. Push/insert the root in the stack.
6. After that, traverse while the size of the stack is not 0. Create a pointer curr of type Node and store the element at the top of the stack in it and pop/delete it from the stack.
7. If the right of the curr is present, update the map at index data of right of curr as the data of curr. Push/insert the right of curr in the stack.
8. If the left of the curr is present, update the map at index data of the left of curr as the data of curr. Push/insert the left of curr in the stack.
9. Similarly, create another function to print the ancestors. Check if the root is equal to null, return.
10. Create an unordered map and set the data of its root as 0.
11. Call the function to set the parents of all nodes.
12. Finally, call the function to print the tree path.

이 문제에 대해 이진 트리가 주어지고 노드의 조상을 인쇄해야합니다. 노드의 자식이있는 것처럼 트리의 루트를 제외한 조상이 있습니다. 나무의 잎사귀를 생각하면 아이가 없습니다. 마찬가지로 루트 노드에는 조상이 없습니다. 여기에 각 노드의 부모를 저장합니다. 그래서 우리가 조상을 인쇄해야 할 때. 우리는 부모를 사용하여 조상을 찾을 것입니다. 우리는 정렬되지 않은 _ 맵 / HashSet 이 작업을 수행합니다. HashSet은 O (1)에서 삽입 / 검색 / 삭제를 허용하기 때문에. 우리는 선형 시간 복잡성으로이 문제를 해결할 수 있습니다. 아래 솔루션에서 우리는 접근 방식과 같은 그래프 검색을 사용하고 있습니다. 횡단 전체 나무. 그리고 순회하는 동안 우리는 각 노드의 부모를 저장합니다. 그런 다음 조상을 인쇄하기 위해지도 (부모를 저장하는)를 횡단하면서 함수를 생성했습니다. 전체 솔루션은 선형 시간 복잡성으로 실행됩니다. 의 위에).

암호

주어진 이진 트리의 조상을 찾는 반복 방법을위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

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

    Node(int data){
        this->data = data;
        this->left = this->right = nullptr;
  }
};

void printTopToBottomPath(unordered_map<int, int> parent, int key){
    while(key = parent[key]){
        cout << key << " ";
    }
    cout << endl;
}

void setParent(Node* root, unordered_map<int, int> &parent){
    
    stack<Node*> stack;
    stack.push(root);

    while(!stack.empty()){
        
        Node* curr = stack.top();
        stack.pop();

        if(curr->right){
           parent[curr->right->data] = curr->data;
           stack.push(curr->right);
        }

        if(curr->left){
           parent[curr->left->data] = curr->data;
           stack.push(curr->left);
        }
    }
}

void printAncestors(Node* root, int node){
    
    if(root == nullptr){
        return;
    }

    unordered_map<int, int> parent;

    parent[root->data] = 0;

    setParent(root, parent);

    printTopToBottomPath(parent, node);
}

int main(){
    Node* root = nullptr;

    root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(7);
    root->left->left = new Node(3);
    root->left->right = new Node(5);
    root->right->left = new Node(8);
    root->right->right = new Node(9);
    root->left->left->left = new Node(4);
    root->left->right->right = new Node(6);
    root->right->right->left = new Node(10);

    int key = 6;
    printAncestors(root, key);

    return 0;
}
5 2 1

주어진 이진 트리의 조상을 찾는 반복적 인 방법을위한 자바 프로그램

import java.util.*;

class Node{
  int data;
  Node left = null, right = null;

  Node(int data){
    this.data = data;
  }
}

class Main{
  
  public static void printTopToBottomPath(Map<Integer, Integer> parent, int key){
    while((key = parent.get(key)) != 0){
      System.out.print(key + " ");
    }
  }

  public static void setParent(Node root, Map<Integer, Integer> parent){
    
    Deque<Node> stack = new ArrayDeque<>();
    stack.add(root);

    while(!stack.isEmpty()){
      
      Node curr = stack.pollLast();

      if(curr.right != null){
        parent.put(curr.right.data, curr.data);
        stack.add(curr.right);
      }

      if(curr.left != null){
        parent.put(curr.left.data, curr.data);
        stack.add(curr.left);
      }
    }
  }

  public static void printAncestors(Node root, int node){
    
    if(root == null){
      return;
    }

    Map<Integer, Integer> parent = new HashMap<>();

    parent.put(root.data, 0);

    setParent(root, parent);

    printTopToBottomPath(parent, node);
  }

  public static void main(String[] args){
      
      Node root = new Node(1);
      root.left = new Node(2);
            root.right = new Node(7);
            root.left.left = new Node(3);
            root.left.right = new Node(5);
            root.right.left = new Node(8);
            root.right.right = new Node(9);
            root.left.left.left = new Node(4);
            root.left.right.right = new Node(6);
            root.right.right.left = new Node(10);

      int key = 6;
    
      printAncestors(root, key);
  }
}
5 2 1

복잡성 분석

시간 복잡성

의 위에), 여기서 N은 주어진 트리의 노드 수입니다. 우리는 전체 트리를 가로 지르고지도를 가로 질러 조상을 인쇄했습니다.

공간 복잡성

의 위에) 무순 맵과 스택에 여분의 공간을 사용했기 때문입니다.

Translate »