1501 두 갈래 나무의 최대 너비와 높이(귀속 소련)

4236 단어 데이터 구조와 알고리즘

1501 두 갈래 나무의 최대 너비와 높이


시간 제한: 1s
공간 제한: 128000KB
제목 레벨: 실버
제목 설명
Description
두 갈래 나무를 보여 최대 너비와 높이를 출력합니다.
입력 설명
Input Description
첫 번째 줄은 정수 n이다.
다음 n줄은 줄마다 두 개의 수가 있는데 i줄의 두 개의 수는 i의 노드가 연결된 두 개 정도의 아들의 번호를 대표한다.만약 어떤 아들이 비어 있지 않으면 0이다.
출력 설명
Output Description
출력은 모두 한 줄로 두 갈래 나무의 최대 너비와 높이를 출력하고 공백으로 구분합니다.
샘플 입력
Sample Input
오
2 3
4 5
0 0
0 0
0 0
샘플 출력
Sample Output
2 3
데이터 범위 및 알림
Data Size & Hint
n<16
기본 첫 번째는 루트 노드입니다.
입력한 순서를 번호로 하다
2-N+1 줄은 이 노드의 왼쪽 아이와 오른쪽 아이를 가리킨다
주의: 두 번째 문제는 극단적인 데이터가 있습니다!
          1
          0 0
이 문제를 너희들은 교묘하게 굴려고 하지 말고, 나에게 솔직하게 검색해 봐라!

사고방식: 이 문제는 두 갈래 나무의 최대 깊이와 넓이를 요구하기 때문에 먼저 깊이와 길이의 개념을 이해하고


깊이값 두 갈래 나무의 층수, 너비는 두 갈래 나무의 각 층 중 노드가 가장 많은 층수를 가리킨다.


So, 구체적인 사고방식은 문제풀이를 보십시오. 자, 더 이상 말하지 않겠습니다. 위의 문제풀이:
  
#include
#include
#include
#include
using namespace std;
int n,a[10000][3],x=-999,s[10000];
void work(int j,int k)//k ，j k j  ； 
{
    s[k]=s[k]+1;//s[k] k ； 
    if(k>x)    x=k;//x ； 
    if(a[j][1]!=0)    work(a[j][1],k+1);// ， ； 
    if(a[j][2]!=0)    work(a[j][2],k+1);// ， ；
}
int cmp(int ax,int by){
    return ax>by;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i][1]>>a[i][2];
    work(1,1);
    sort(s+1,s+1+10000,cmp);/* ， 1000 ，
     ， ；*/ 
    cout<1]<<" "<<x;
}

 
만약 당신에게 도움이 된다면, 호평을 덧붙이는 것을 잊지 마세요.뽀뽀!!다음에 봐요!88
다음으로 전송:https://www.cnblogs.com/cangT-Tlan/p/6154833.html
【bfs 대기열】102 두 갈래 나무의 층계가 두루 다니다
두 갈래 나무 뒷차례가 흐르는 비귀속 실현

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage