이 진 트 리 복원
입력 형식:
입력 은 먼저 정수 N (≤ 50) 을 드 리 고 나무의 결점 총수 입 니 다.다음 두 줄 은 선착순 과 중 서 를 차례로 보 여 줍 니 다. 모두 길이 가 N 인 중복 영문 자모 (대소 문자 구별) 가 포함 되 지 않 은 문자열 입 니 다.
출력 형식:
출력 은 이 두 갈래 나무의 높이 인 정수 입 니 다.
입력 예시:
9
ABDFGHIEC
FDHGIBEAC
출력 예시:
5먼저 옮 겨 다 니 는 순 서 는 뿌리 - > 왼쪽 트 리 - > 오른쪽 트 리 입 니 다.
중간 순 서 는 왼쪽 트 리 - > 뿌리 - > 오른쪽 트 리 입 니 다.
다음 순서 로 옮 겨 다 니 는 순 서 는: 왼쪽 트 리 - > 오른쪽 트 리 - > 뿌리
전역 변 수 를 사용 하여 배열 을 정의 합 니 다. 재 귀 할 때 다음 값 만 전달 하고 배열 을 전달 하지 않 아 도 됩 니 다.
이 문 제 는 높이 를 구 하 는 것 이기 때문에 노드 의 데이터 와 관련 되 지 않 기 때문에 구조 체 에서 data 를 정의 할 필요 가 없고 나무의 구 조 를 구축 하면 된다.
첫 번 째 데 이 터 는 반드시 나무 뿌리 입 니 다. 중간 순서 배열 에 있 는 위 치 를 검색 하여 중간 순서 배열 을 왼쪽 서브 트 리 와 오른쪽 서브 트 리 로 나 누 는 동시에 왼쪽 글자 노드 의 갯 수 에 따라 먼저 순서 배열 을 좌우 서브 트 리 로 나 눕 니 다.이렇게 한 번 의 구분 을 한 후에 좌우 서브 트 리 의 순서 와 중간 순 서 를 확정 하고 재 귀 를 이용 하여 구분 했다.좌우 나무 가 언제 없 는 지 를 고려 해 야 한다. 답 은 분명 하 다. 뿌리 를 이용 해 중간 배열 을 나 눈 후 남 은 요소 가 없다 는 것 이다.
#include
#include
typedef struct node* Ptr;
struct node{
Ptr left;
Ptr right;
};
char pre[50],in[50];
int num;
// 、 、
Ptr Restore( int preMin, int preMax, int inMin, int inMax);
int GetHeight( Ptr head);
int main(void){
Ptr BT;
int height;
scanf("%d", &num);
scanf("%s", pre);
scanf("%s", in);
BT = Restore( 0, num - 1, 0, num - 1);
height = GetHeight( BT);
printf("%d", height);
return 0;
}
Ptr Restore( int preMin, int preMax, int inMin, int inMax){
Ptr root;
int i;
root = (Ptr)malloc(sizeof(struct node));
root->left = root->right = NULL;
for( i = inMin; i <= inMax; i++){
if( pre[preMin] == in[i]){
if( i != inMin) root->left = Restore( preMin + 1, preMin + inMin - 1, inMin, i - 1); //
if( i != inMax) root->right = Restore( preMin + i - inMin + 1, preMax, i + 1, inMax);//
break;
}
}
return root;
}
int GetHeight( Ptr head){
int hl, hr, max;
if( head == NULL) return 0;
else{
hl = GetHeight( head->left);
hr = GetHeight( head->right);
max = hl > hr ? hl : hr;
}
return max + 1;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
