A 1138 Postorder Traversal (25분) (두 갈래 나무는 선순, 중순, 후순을 알고 있음)

1278 단어

1. 기술 총결산

  • 중서열을 포함하는 것으로 알고 있습니다. 선서나 후서열을 마음대로 알면 두 갈래 트리를 확정할 수 있습니다.create 함수 템플릿은 기억해야 합니다.root->data=in[k]부치를 잊지 마세요.반환 경계, 반환은 return NULL..
  • 동시에, 뒷차례가 두루 훑어보았습니다.return에는 없는..

  • 2. 참조 코드

    #include
    #include
    using namespace std;
    struct node{
    	int v;
    	node *L, *R;
    }; 
    vector in, pre, post;
    node* create(int preL, int preR, int inL, int inR){
    	if(preL > preR){
    		return NULL;
    	}
    	node *root = new node;
    	int k;
    	for(k = inL; k <= inR; k++){
    		if(in[k] == pre[preL]){
    			break;
    		}
    	}
    	int num = k - inL;
    	root->v = in[k];
    	root->L = create(preL+1, preL + num, inL, k - 1);
    	root->R = create(preL + num + 1, preR, k + 1, inR);
    	return root;
    }
    void postorder(node *root){
    	if(root == NULL){
    		return;
    	}
    	postorder(root->L);
    	postorder(root->R);
    	post.push_back(root->v);
    }
    int main(){
    	int n, num;
    	scanf("%d", &n);
    	for(int i = 0; i < n; i++){
    		scanf("%d", &num);
    		pre.push_back(num);
    	}
    	for(int i = 0; i < n; i++){
    		scanf("%d", &num);
    		in.push_back(num); 
    	}
    	node *root = create(0, n-1, 0, n-1);
    	postorder(root);
    	printf("%d", post[0]);
    	return 0;
    }
    

    좋은 웹페이지 즐겨찾기