6 - 3 이 진 트 리 의 최근 공공 조상 검색 (25 분)

빅 뱅 반기 데이터 구조
이 진 트 리 의 최근 공공 조상 을 수색 하 다.

나무 한 그루 T 중 두 개의 결점 u 과 v 의 최근 공공 조상 (LCA) 은 나무 중에서 u 과 v 를 후손 으로 하 는 깊이 가 가장 큰 결점 이다.현재 한 두 갈래 검색 트 리 (BST) 중 임의의 두 개의 결점 을 정 해 최근 의 공공 조상 을 찾 아 보라 고 한다.
함수 인터페이스 정의:

int LCA( Tree T, int u, int v );

그 중에서 Tree 의 정 의 는 다음 과 같다.

typedef struct TreeNode *Tree;
struct TreeNode {
    int   Key;
    Tree  Left;
    Tree  Right;
};

함수 LCA 는 나무 T 의 두 결점 u 과 v 의 최근 공공 조상 결점 의 키 를 되 돌려 야 한다.u 또는 v 나무 에 없 으 면 되 돌아 와 야 한다 ERROR.
심판 테스트 프로그램 샘플:

#include 
#include 

#define ERROR -1
typedef struct TreeNode *Tree;
struct TreeNode {
    int   Key;
    Tree  Left;
    Tree  Right;
};

Tree BuildTree(); /*        */
int LCA( Tree T,  int u, int v );

int main()
{
    Tree T;
    int u, v, ans;

    T = BuildTree();
    scanf("%d %d", &u, &v);
    ans = LCA(T, u, v);
    if ( ans == ERROR ) printf("Wrong input
");
    else printf("LCA = %d
", ans);

    return 0;
}

/*            */

문제 풀이:

int find(Tree T,int u)

{
	if(!T)
	return 0;
	if(T->Key==u)
	return 1;
	if(T->KeyRight,u);
	if(T->Key>u)
	return find(T->Left,u);
	
}
int LCA( Tree T, int u, int v )
{
	if(!T)
	return ERROR;
	if(!find(T,u)||!find(T,v))
	return ERROR;
	if(u==T->Key||v==T->Key)
	return T->Key;
	if(uKey&&v>T->Key||u>T->Key&&vKey)
	return T->Key;
	if(u>T->Key)
	return LCA(T->Right,u,v);
	if(uKey)
	return LCA(T->Left,u,v); 
	
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

PTA: 6 - 5 싱글 체인 테이블 짝수 노드 삭제 (20 점)

빅 뱅 반기 데이터 구조 데이터 구조 제목 집합 단일 체인 테이블 짝수 노드 삭제 이 문 제 는 두 가지 함 수 를 실현 하고 읽 은 데 이 터 를 단일 체인 표 로 저장 하 며 링크 의 쌍 수 치 를 삭제 해 야 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

6 - 3 이 진 트 리 의 최근 공공 조상 검색 (25 분)

좋은 웹페이지 즐겨찾기