NOIP 보급 2001, 우선 순위 지정

8324 단어 나무.

[두 갈래 나무] 선순 배열을 구하다


전송문: 순서 배열 구하기
  가 두 갈래 나무의 선순과 중순을 구한 후순, 그리고 후순과 중순을 구한 문제는 두 갈래 나무의 가장 기초적인 문제(蒻방금 배운 나무)에 관한 것이다. 이 세 가지 역행 방법의 차이는 뿌리 노드의 역행 순서와 관련이 있다. 모두 역귀로 실현할 수 있다.마지막으로 선서근으로 오른쪽 트리를 훑어본다. 선서근으로 왼쪽 트리를 훑어본 다음에 뿌리 노드를 방문하고 마지막으로 중서근으로 오른쪽 트리를 훑어본다. 선서근으로 왼쪽 트리를 훑어본 다음에 후서근으로 오른쪽 트리를 훑어본다. 마지막으로 뿌리 노드를 방문하는 세 가지 훑어보는 방식은 두 갈래 트리 내용의 기초이다.여기서 더 이상 군말 하지 않겠다
   우리는 이 문제를 되돌아본다. 왜냐하면 뒷차례 역력의 특성 때문에 뒷차례 역력의 마지막 노드는 바로 이 두 갈래 나무의 뿌리이다. 뿌리를 알게 된 후에 다시 중차례 역력을 본다. 왜냐하면 중차례 역력은 먼저 왼쪽 나무, 그 다음에 뿌리, 마지막에 오른쪽 나무에 방문하기 때문이다. 그래서 중차례 역력 서열의 마지막 노드를 경계로 하고 왼쪽은 왼쪽 나무의 중차례 역력이다.오른쪽이 바로 오른쪽 나무의 중차 역행 서열이다.그렇다면 어떻게 왼쪽 나무와 오른쪽 나무의 뒷차례가 차례차례 차례차례 서열을 훑어보는 것을 구할 수 있습니까?중서열 서열로 우리는 왼쪽 트리와 오른쪽 트리의 노드 수(즉 서열 길이)를 구할 수 있다. 그리고 뒷서열의 왼쪽은 왼쪽 트리, 오른쪽은 오른쪽 트리를 구할 수 있다. 그러면 우리는 길이를 알고 뒷서열의 시작 좌표에 왼쪽 트리의 길이를 더한다. 이 단락이 바로 왼쪽 트리의 뒷서열이다.그 다음은 뿌리를 먼저 출력한 다음에 왼쪽 나무와 오른쪽 나무의 길이를 보고 틈틈이 돌려서 출력하는 것이 아니다 (그래서 나무를 세울 필요가 없다?)  는 약간 감돌 수 있지만 뒷차례가 지나가는 마지막은 뿌리 노드라는 것을 알면 중간차례가 뿌리 노드의 위치를 찾으면 왼쪽은 왼쪽 나무이고 오른쪽은 오른쪽 나무이다.다른 건 다 디테일한 문제야~
  는 그 문제를 시작하는 AC 코드를 붙입니다.
#include
#include
#include
using namespace std;
char in[10],post[10];
int lena,lenb;
void f(int,int,int,int);
int main(){
	ios::sync_with_stdio(false);
	cin>>in>>post;
	lena=strlen(in);
	lenb=strlen(post);
	f(0,lena-1,0,lenb-1);
	
	return 0;
} 
void f(int lin,int rin,int lpost,int rpost){
	// （ ） 
	cout<<post[rpost];
	// ， 
	int idx;
	for(int i=lin;i<=rin;i++){
		if(in[i]==post[rpost]){
			idx=i;
			break;
		}
	} 
	// ， 
	if(idx-1 >= lin){
		f(lin,idx-1,lpost,lpost+(idx-1-lin));
	} 
	// ， 
	if(idx+1 <= rin){
		f(idx+1,rin,lpost+(idx-1-lin)+1,rpost-1);
	} 
}

(AC가 쉽지 않아요. 여러분, 좋아요 안 눌러요?
검지offer 시리즈의 23: 두 갈래 나무 중 하나는 모든 경로가 될 만한
비귀속 실현 전순, 중순, 후순 두 갈래 트리

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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