제목 1368: 두 갈래 나무와 어떤 값의 경로 - 9도
두 갈래 트리와 정수를 입력하고 두 갈래 트리의 결점 값과 정수를 입력하기 위한 모든 경로를 출력합니다.경로는 나무의 뿌리 결점에서 시작하여 잎 결점까지 내려가는 결점으로 경로를 형성합니다.
입력:
각 테스트 사례에는 n+1 행이 포함됩니다.
첫 번째 행위는 2개의 정수 n, k(1<=n<=10000), n은 결점의 개수를 나타내고, k는 요구하는 경로와 결점 번호를 1부터 n까지 나타낸다.
다음은 n줄이 있다.이 n행에서 매 행위 3개의 정수vi,leftnode,rightnode,vi는 i번째 결점의 값을 나타내고,leftnode는 i번째 결점의 왼쪽 아이의 결점 번호를 나타내고,rightnode는 i번째 결점의 오른쪽 아이의 결점 번호를 나타내며, 결점 값이 없으면 -1이다.번호가 1인 결점은 루트 결점입니다.
출력:
모든 테스트 사례에 대응하여 "result:"를 출력하여 한 줄을 차지하고 다음에 사전 순서에 따라 조건을 충족시키는 모든 경로를 출력합니다. 이 경로는 결점 번호로 구성되고 출력 형식은 출력 샘플을 참조합니다.
샘플 입력:
5 22
10 2 3
5 4 5
12 -1 -1
4 -1 -1
7 -1 -1
1 5
1 -1 -1
샘플 출력:
result:
A path is found: 1 2 5
A path is found: 1 3
result:
추천 지수: ※
출처:http://ac.jobdu.com/problem.php?pid=1368
PAT의http://blog.csdn.net/zhu_liangwei/article/details/9735741유사하다.
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<vector>
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
typedef struct node{
int val;
int left;
int right;
}node;
vector<int> path;
void print_path(){
printf("A path is found:");
for(int i=0;i<path.size();i++){
printf(" %d",path[i]);
}
printf("
");
}
void find_fit_path(int curr,int i,const node *t){
if(i!=-1&&t[i].val==curr&&-1==t[i].left&&-1==t[i].right){
path.push_back(i);
print_path();
path.pop_back();
}
else if(t[i].val<curr){
int tmp=min(t[i].left,t[i].right);
path.push_back(i);
if(tmp!=-1)
find_fit_path(curr-t[i].val,tmp,t);
tmp=max(t[i].left,t[i].right);
if(tmp!=-1)
find_fit_path(curr-t[i].val,tmp,t);
path.pop_back();
}
}
int main()
{
int n,k,i;
while(scanf("%d%d",&n,&k)!=EOF){
node *tree=new node[n+1];
for(i=1;i<=n;i++)
scanf("%d%d%d",&tree[i].val,&tree[i].left,&tree[i].right);
printf("result:
");
find_fit_path(k,1,tree);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
