부모 배열의 일반 트리 높이  


난이도 중급
자주 묻는 질문 구글 알레그로 퀄컴 스프링클러 동네 짱
폭 우선 검색 동적 프로그래밍 Graph 나무

문제 정책  

“부모 배열의 일반 트리 높이”문제는 배열 par [0… n-1]로 n 개의 정점이있는 트리가 제공된다는 것을 나타냅니다. 여기서 par []의 모든 인덱스 i는 노드를 나타내고 i의 값은 해당 노드의 직계 부모를 나타냅니다. 부모가없는 루트 노드의 경우 par [] 배열의 값은 -1입니다. 이제 우리는 부모 연결이 주어진 나무의 높이를 찾아야합니다.

아래 주어진 par [] 배열을 고려하십시오.

부모 배열의 일반 트리 높이

이러한 par [] 배열 연결을 사용하여 구성된 트리는 다음과 같습니다.

부모 배열의 일반 트리 높이

참고 : 나무의 높이는 100 단위를 넘을 수 없습니다.

부모 배열의 일반 트리 높이

예  

[-1 0 0 1 2 2 4]
3

설명 : 가장 긴 경로의 가장자리 수는 3입니다.

[-1 0 0 1 1 2 2 3 3 4 7]
4

설명 : 가장 긴 경로 (0-> 1-> 3-> 7-> 10)의 가장자리 수는 4입니다.

솔루션 유형  

  1. 폭 우선 검색
  2. 동적 프로그래밍

폭 우선 검색  

부모 배열에서 일반 트리의 높이를 찾는 방법

이 문제를 해결하기 위해 주어진 par [] 배열을 사용하여 트리 (그래프 데이터 구조)를 구성합니다. 이제 루트 노드에서 시작하여 BFS를 수행하고 트리 경로를 따라 가장 긴 경로 (또는 가장 먼 정점의 거리)를 찾습니다. 따라서이 거리 자체의 값을 나무의 높이라고합니다. BFS는 전체 그래프를 순회하는 그래프 순회 알고리즘 일뿐입니다. 폭 우선 검색 현재 노드에 가장 가까운 노드가 더 많은 거리를 가진 노드보다 먼저 이동하도록 작동합니다. 이렇게하면 루트에서 각 노드의 거리를 찾을 수 있습니다. 그리고 거리가 가장 큰 노드를 나무 높이의 노드라고합니다.

참조
강력하게 연결된 구성 요소

암호알고리즘

1. Construct the directed graph using the par[] array values.
2. The edges in graph should be directed from node par[i] to i. i.e, par[i] --> i.
3. The root node has no parent and hence, no incoming edge.
4. Now starting from the root node, perform BFS, and calculate distance of each of the nodes in the tree from the root node itself.
5. The largest distance value is the height of the tree.

 

알고리즘은 다음과 같습니다.

부모 배열의 일반 트리 높이

부모 배열의 일반 트리 높이

BFS를 사용하는 일반 트리의 높이

암호

부모 배열에서 일반 트리의 높이를 찾는 C ++ 프로그램

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

// perform BFS to calculate Height
int BFS(vector <int> par)
{
    int root;
    int n = par.size();
    vector <int> graph[n];
    
    // construct graph from given parent array
    for(int i=0;i<n;i++)
    {
        if(par[i] != -1)
        graph[par[i]].push_back(i);    
        
        else
        root = i;
    }
    
    // to store distance of each node from the root
    vector <int> distance(n,0);
    
    // create BFS queue
    queue <int> q;
    // insert the root node
    q.push(root);
    
    // Begin BFS & calculate distance of each node from root
    while(!q.empty())
    {
        int front = q.front();
        q.pop();
        
        for(auto i : graph[front])
        {
            distance[i] = distance[front] + 1;
            q.push(i);
        }
    }
    
    // return height of the Tree
    return *max_element(distance.begin(),distance.end());
}

int main()
{
    // define parent array
    vector <int> par = {-1,0,0,1,2,2,4};
    cout<<"Height of the Tree : "<<BFS(par)<<endl;
    return 0;
}
Height of the Tree : 3

부모 배열에서 일반 트리의 높이를 찾는 Java 프로그램

import java.util.*;
import java.io.*;

class TutorialCup 
{
    // perform BFS to calculate Height
    static int BFS(int [] par)
    {
        int root = 0;
        int n = par.length;
        ArrayList <ArrayList <Integer>> graph = new ArrayList<ArrayList<Integer>>();
        
        // construct graph from given parent array
        for(int i=0;i<n;i++)
        {
            graph.add(new ArrayList<Integer>());
            
            if(par[i] != -1)
            graph.get(par[i]).add(i);    
            
            else
            root = i;
        }
        
        // to store distance of each node from the root
        int distance[] = new int[n];
        
        // create BFS queue
        Queue <Integer> q = new LinkedList<>();
        // insert the root node
        q.add(root);
        
        // Begin BFS & calculate distance of each node from root
        while(!q.isEmpty())
        {
            int front = q.poll();
            
            Iterator itr = graph.get(front).iterator();
            
            while(itr.hasNext())
            {
                int i = (Integer)itr.next();
                distance[i] = distance[front] + 1;
                q.add(i);
            }
        }
        
        // return height of the Tree
        int height = 0;
        for(int i=0;i<distance.length;i++)
        height = Math.max(height,distance[i]);
        
        return height;
    }
    
    public static void main (String[] args)
    {
        // define parent array
        int [] par = {-1,0,0,1,2,2,4};
        System.out.println("Height of the Tree : "+BFS(par));
    }
}
Height of the Tree : 3

복잡성 분석

시간 복잡성

T (n) = O (V + E) = O (2V-1) = O (V). 여기에서는 전체 트리를 포함하여 총 V 개의 정점을 포함하는 너비 우선 검색을 수행했습니다. 따라서 선형 시간 복잡성을 제공합니다.

참조
이진 트리에서 삭제

공간 복잡성

A (n) = O (V), 생성 된 BFS 대기열 및 그래프 트리의 경우. 최악의 경우 모든 노드가 루트가 아닌 동일한 부모를 갖는 스타 트리를 가질 수 있습니다. 따라서이 경우 O (V)가 될 최악의 공간 복잡성이 달성됩니다.

어디에,

V = 트리의 정점 수.

E = 나무의 모서리 수 = V-1

동적 프로그래밍  

부모 배열에서 일반 트리의 높이를 찾는 방법

안에 나무 N 개 노드 중 0부터 N-1까지 순서대로 각 노드를 방문합니다. 각 노드에 대해 함수를 사용하여 높이를 계산하십시오. findHeight () (노드의 높이는 특정 노드와 루트 노드 사이의 가장자리 수입니다).

노드의 높이를 계산하기 전에 모든 조상 노드의 높이를 재귀 적으로 계산해야합니다. 그만큼 findDistance () 이 작업을 재귀 적으로 수행. 트리에서 노드의 높이를 계산 한 후. 방문한 것으로 표시되어야합니다 (방문 함 [] 배열이이 목적으로 사용됨).

암호알고리즘

1. Define two functions findDistance( ) & findHeight( ) for calculating height of each node in the tree.
2. Visit each node iteratively in order from 0 to V-1 (where V = number of vertices).
3. For a particular node, calculate heights of all it's ancestors recursively before the calculating height of the node itself, this is done using findDistance() recursive function.
4. every ancestor node visited should be marked as visited (using visited[ ] array).
5. Return the maximum value in the height[ ].
6. steps 1 to 5 are encapsulated in findHeight( ) function.

 

동적 프로그래밍을 사용하는 나무의 높이

 

암호

부모 배열에서 일반 트리의 높이를 찾는 C ++ 프로그램

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

// function to find height of node - i from tree root
int findDistance(vector <int> par, int i, vector <bool> &visited, vector <int> &height)
{
    // if root node is encountered
    if(par[i] == -1)
    {
        visited[i] = true;
        return 0;
    }
    
    // if node is already visited
    // return it's calculated height
    if(visited[i])
    return height[i];
    
    // if a node is not visited
    // below steps are executed
    
    // mark node visited
    visited[i] = true;
    // calculate height of node
    height[i] = 1+findDistance(par,par[i],visited,height);
    // return height after calculation    
    return height[i];
}

// function to calculate maximum height
int findHeight(vector <int> par)
{
    int maxHeight = 0;
    
    int n = par.size();
    
    // visited array is used to check if a node is visited
    vector <bool> visited(n,false);
    // calculate height of each node in the tree
    vector <int> height(n,0);
    
    // traverse each node of the tree
    // evaluate height of each node & store maximum of all heights 
    for(int i=0;i<n;i++)
    {
        height[i] = findDistance(par,i,visited,height);
        maxHeight = max(maxHeight,height[i]);
    }
    
    // return maximum of all heights
    return maxHeight;
}

int main()
{
    // define parent array
    vector <int> par = {-1,0,0,1,2,2,4};
    cout<<"Height of the Tree : "<<findHeight(par)<<endl;
    return 0;
}
Height of the Tree : 3

부모 배열에서 일반 트리의 높이를 찾는 Java 프로그램

import java.util.*;
import java.io.*;

class TutorialCup 
{
    // function to find height of node - i from tree root
    static int findDistance(int [] par, int i, boolean [] visited, int [] height)
    {
        // if root node is encountered
        if(par[i] == -1)
        {
            visited[i] = true;
            return 0;
        }
        
        // if node is already visited
        // return it's calculated height
        if(visited[i] == true)
        return height[i];
        
        // if a node is not visited
        // below steps are executed
        
        // mark node visited
        visited[i] = true;
        // calculate height of node
        height[i] = 1+findDistance(par,par[i],visited,height);
        // return height after calculation    
        return height[i];
    }

    // function to calculate maximum height
    static int findHeight(int [] par)
    {
        int maxHeight = 0;
        
        int n = par.length;
        
        // visited array is used to check if a node is visited
        boolean [] visited = new boolean[n];
        // calculate height of each node in the tree
        int [] height = new int[n];
        
        // traverse each node of the tree
        // evaluate height of each node & store maximum of all heights 
        for(int i=0;i<n;i++)
        {
            height[i] = findDistance(par,i,visited,height);
            maxHeight = Math.max(maxHeight,height[i]);
        }
        
        // return maximum of all heights
        return maxHeight;
    }
    
    public static void main (String[] args)
    {
        // define parent array
        int [] par = {-1,0,0,1,2,2,4};
        System.out.println("Height of the Tree : "+findHeight(par));
    }
}
Height of the Tree : 3

복잡성 분석

시간 복잡성

의 위에),  여기에서도 트리의 모든 노드를 횡단 할 것이기 때문입니다. 우리는 트리의 모든 노드를 순회 할 것입니다. 이로 인해 선형 시간 복잡도 O (N)를 달성했습니다. 여기서 N은 트리의 노드 수를 나타냅니다.

참조
가장 긴 올바른 대괄호 하위 시퀀스에 대한 범위 쿼리

공간 복잡성

의 위에), 각 노드의 높이를 저장해야합니다. 현재 노드의 자식이 사용할 때 사용됩니다. 따라서 알고리즘은 선형 공간 복잡성을 갖습니다.