1368: 두 갈래 트리와 같은 값의 경로 @jobdu
제목 1368: 두 갈래 트리 중 하나가 되는 경로
시간 제한: 1초
메모리 제한: 32메가바이트
특수 판제: 아니요
제출: 1238
해결
제목 설명:
두 갈래 트리와 정수를 입력하고 두 갈래 트리의 결점 값과 정수를 입력하기 위한 모든 경로를 출력합니다.경로는 나무의 뿌리 결점에서 시작하여 잎 결점까지 내려가는 결점으로 경로를 형성합니다.
입력:
각 테스트 사례에는 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 2210 2 35 4 512 -1 -14 -1 -17 -1 -11 51 -1 -1샘플 출력:
result:A path is found: 1 2 5A path is found: 1 3result:문제 해결:
문제를 풀다문제 풀이 소감 공유?토론 주제는 다음을 참조하십시오.http://t.jobdu.com/thread-8091-1-1.html
import java.io.BufferedInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;
public class S25 {
public static void main(String[] args) throws FileNotFoundException {
BufferedInputStream in = new BufferedInputStream(new FileInputStream("in.in"));
System.setIn(in);
Scanner cin = new Scanner(System.in);
while (cin.hasNextInt()) {
int n = cin.nextInt();
int k = cin.nextInt();
TreeNode[] tree = new TreeNode[n+1];
for(int i=0; i<n; i++){
if(tree[i] == null){
tree[i] = new TreeNode(cin.nextInt(), i+1);
}
int leftIdx = cin.nextInt();
int rightIdx = cin.nextInt();
if(leftIdx > rightIdx){
int tmp = leftIdx;
leftIdx = rightIdx;
rightIdx = tmp;
}
tree[i].left = new TreeNode(0, leftIdx);
tree[i].right = new TreeNode(0, rightIdx);
}
for(int i=0; i<n; i++){
if(tree[i].left.idx != -1){
tree[i].left = tree[tree[i].left.idx-1];
}else{
tree[i].left = null;
}
if(tree[i].right.idx != -1){
tree[i].right = tree[tree[i].right.idx-1];
}else{
tree[i].right = null;
}
}
// preorder(tree[0]);
ArrayList<ArrayList<Integer>> ret = printPath(tree[0], k);
System.out.println("result:");
for (ArrayList<Integer> al : ret) {
System.out.print("A path is found:");
for (Integer val : al) {
System.out.print(" " + val);
}
System.out.println();
}
}
}
private static ArrayList<ArrayList<Integer>> printPath(TreeNode root, int k) {
ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> al = new ArrayList<Integer>();
rec(root, k, al, ret);
return ret;
}
private static void rec(TreeNode root, int k, ArrayList<Integer> al, ArrayList<ArrayList<Integer>> ret){
if(root == null){
return;
}
if(root.val == k){
al.add(root.idx);
ret.add(new ArrayList<Integer>(al));
al.remove(al.size()-1);
return;
}
al.add(root.idx);
rec(root.left, k-root.val, al, ret);
rec(root.right, k-root.val, al, ret);
al.remove(al.size()-1);
}
private static void preorder(TreeNode root){
if(root != null){
System.out.print(root.val + " ");
preorder(root.left);
preorder(root.right);
}
}
public static class TreeNode{
int val;
int idx;
TreeNode left, right;
public TreeNode(int val_, int idx_){
val = val_;
idx = idx_;
}
}
}
AC:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Stack;
public class Main {
/*
* 1368
*/
private static BinaSortTree[] biTrees;
private static int valueArr[];
private static int k ;
public static void main(String[] args) throws Exception {
StreamTokenizer st = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
while (st.nextToken() != StreamTokenizer.TT_EOF) {
int n = (int) st.nval;
st.nextToken();
k = (int) st.nval;
biTrees = new BinaSortTree[n+1];
valueArr = new int[n+1];
for (int i = 1; i < n+1; i++) {
st.nextToken();
valueArr[i] = (int)st.nval;
st.nextToken();
int left = (int)st.nval;
st.nextToken();
int right = (int)st.nval;
BinaSortTree leftTree = null;
BinaSortTree rightTree = null;
if (left != -1 && right != -1) {
int temp = left;
left = Math.min(left, right);
right = Math.max(temp, right);
}
if (left != -1) {
leftTree = new BinaSortTree(left);
}
if (right != -1) {
rightTree = new BinaSortTree(right);
}
biTrees[i] = new BinaSortTree(leftTree, rightTree ,i);
}
createTree(biTrees[1]);
int sum = 0;
Stack<Integer> stack = new Stack<Integer>();
System.out.println("result:");
printPath(biTrees[1] , sum, stack );
}
}
private static void createTree(BinaSortTree binaSortTree) {
if (binaSortTree == null) {
return;
}
Stack<BinaSortTree> treeStack = new Stack<BinaSortTree>();
treeStack.push(binaSortTree);
while (!treeStack.isEmpty()) {
BinaSortTree biTree = treeStack.peek();
if (biTree.lchild != null) {
biTree.lchild = biTrees[biTree.lchild.value];
createTree(biTree.lchild);
}
if (biTree.rchild != null) {
biTree.rchild = biTrees[biTree.rchild.value];
createTree(biTree.rchild);
}
treeStack.pop();
}
}
private static void printPath(BinaSortTree root,int sum,Stack<Integer> stack){
if(root != null){
sum = sum + valueArr[root.value];
stack.push(root.value);
printPath(root.lchild, sum, stack);
printPath(root.rchild, sum, stack);
if(sum == k && root.lchild == null && root.rchild == null){
printfStack(stack);
}
stack.pop();
}
}
private static void printfStack(Stack<Integer> stack) {
System.out.printf("A path is found: ");
StringBuffer sb = new StringBuffer();
for(int num:stack){
sb.append(num+" ");
}
System.out.printf(sb.toString().trim());
System.out.println();
}
private static class BinaSortTree {
private BinaSortTree lchild;
private BinaSortTree rchild;
private int value ;
public BinaSortTree(int value) {
super();
this.value = value;
}
public BinaSortTree(BinaSortTree lchild, BinaSortTree rchild, int value) {
super();
this.lchild = lchild;
this.rchild = rchild;
this.value = value;
}
}
}
/**************************************************************
Problem: 1368
User: wzqwsrf
Language: Java
Result: Accepted
Time:1310 ms
Memory:63380 kb
****************************************************************/이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
