9도 OJ 1350: 두 갈래 나무의 깊이(두 갈래 나무)

시간 제한: 1초
메모리 제한: 32메가바이트
특수 판제: 아니요
제출: 1044
해결
제목 설명:
이 나무의 깊이를 구하려면 두 갈래 나무를 입력하십시오.뿌리 결점에서 잎 결점까지 순서대로 지나가는 결점(뿌리, 잎 결점 포함)은 나무의 경로를 형성하고 가장 긴 경로의 길이는 나무의 깊이이다.
입력:
첫 번째 줄의 입력은 n, n으로 결점 수를 표시하고 결점 번호는 1부터 n까지입니다.루트 결점은 1입니다.n <= 10.
다음은 n줄이 있는데 줄마다 두 개의 정형 a와 b가 있는데 이것은 i번째 노드의 좌우 아이를 나타낸다.a는 왼쪽 아이, b는 오른쪽 아이입니다.a가 -1일 때 왼쪽 아이가 없다.b가 -1일 때 오른쪽 아이가 없다.
출력:
트리의 깊이를 나타내는 정형을 내보냅니다.
샘플 입력:
32 3-1 -1-1 -1

샘플 출력:
2

생각:
두 갈래 나무의 정의에 따라 업데이트를 차례로 찾습니다.
코드:
#include <stdio.h>
 
#define N 10
 
int left[N+1], right[N+1];
 
int func(int i)
{
    if (left[i] == -1 && right[i] == -1)
        return 0;
    int dleft = (left[i] == -1) ? 0 : func(left[i]);
    int dright = (right[i] == -1) ? 0 : func(right[i]);
    return dleft > dright ? dleft+1 : dright+1;
}
 
int main(void)
{
    int n, i;
 
    while (scanf("%d", &n) != EOF)
    {
        for(i=1; i<=n; i++)
            scanf("%d%d", &left[i], &right[i]);
 
        printf("%d
", func(1)+1); } return 0; } /************************************************************** Problem: 1350 User: liangrx06 Language: C Result: Accepted Time:0 ms Memory:912 kb ****************************************************************/

좋은 웹페이지 즐겨찾기