1523:ツリーを上から下へ印刷@jobdu
3042 ワード
基本的な問題は、普通のLevel Order Traversalです.
タイトル1523:ツリーを上から下へ印刷
時間制限:1秒
メモリ制限:128メガ
特殊問題:いいえ
コミット:384
解決:156
タイトルの説明:
ツリーの各ノードを上から下に印刷し、同レイヤノードを左から右に印刷します.
入力:
入力には複数のテストサンプルが含まれ、入力はEOFで終了します.各テストケースについて、入力する最初の行の整数n(1<=n<=1000、:nは入力するツリー要素の個数(ノード1から番号付け)を表します.次の行には、i番目のツリーノードの要素の値を表すn個の数字があります.次はn行で、各行に1文字Ciがあります.Ci=’d’は,i番目のノードに2人の子があり,次いで左の子番号と右の子番号であることを示す.Ci=’l’は、i番目のノードに左の子があり、左の子の番号が続くことを示す.Ci=’r’は、i番目のノードに右の子があり、右の子の番号が続くことを示す.Ci=’z’はi番目のノードに子供がいないことを示す.
出力:
各テストケースに対応して、ツリーノードの値を上下から左から右に印刷します.
サンプル入力:
サンプル出力:
タイトル1523:ツリーを上から下へ印刷
時間制限:1秒
メモリ制限:128メガ
特殊問題:いいえ
コミット:384
解決:156
タイトルの説明:
ツリーの各ノードを上から下に印刷し、同レイヤノードを左から右に印刷します.
入力:
入力には複数のテストサンプルが含まれ、入力はEOFで終了します.各テストケースについて、入力する最初の行の整数n(1<=n<=1000、:nは入力するツリー要素の個数(ノード1から番号付け)を表します.次の行には、i番目のツリーノードの要素の値を表すn個の数字があります.次はn行で、各行に1文字Ciがあります.Ci=’d’は,i番目のノードに2人の子があり,次いで左の子番号と右の子番号であることを示す.Ci=’l’は、i番目のノードに左の子があり、左の子の番号が続くことを示す.Ci=’r’は、i番目のノードに右の子があり、右の子の番号が続くことを示す.Ci=’z’はi番目のノードに子供がいないことを示す.
出力:
各テストケースに対応して、ツリーノードの値を上下から左から右に印刷します.
サンプル入力:
7
8 6 5 7 10 9 11
d 2 5
d 3 4
z
z
d 6 7
z
z
サンプル出力:
8 6 10 5 7 9 11
import java.io.BufferedInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Scanner;
public class S23 {
static int loop = 0;
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();
loop = n;
int[] tmp = new int[n];
for(int i=0; i<n; i++){
tmp[i] = cin.nextInt();
}
// System.out.println(Arrays.toString(tmp));
if(n == 0){
System.out.println("NULL");
continue;
}
cin.nextLine();
TreeNode[] tree = new TreeNode[n];
for(int i=0; i<n; i++){
String s = cin.nextLine();
//System.out.println(s);
String[] ss = s.split(" ");
if(tree[i] == null){ // ! !
tree[i] = new TreeNode(tmp[i]);
}
if(ss[0].equals("d")){
int left = Integer.parseInt(ss[1]);
int right = Integer.parseInt(ss[2]);
if(tree[left-1]==null)
tree[left-1] = new TreeNode(tmp[left-1]);
if(tree[right-1]==null)
tree[right-1] = new TreeNode(tmp[right-1]);
tree[i].left = tree[left-1];
tree[i].right = tree[right-1];
}else if(ss[0].equals("l")){
int left = Integer.parseInt(ss[1]);
tree[left-1] = new TreeNode(tmp[left-1]);
tree[i].left = tree[left-1];
}else if(ss[0].equals("r")){
int right = Integer.parseInt(ss[1]);
tree[right-1] = new TreeNode(tmp[right-1]);
tree[i].right = tree[right-1];
}else if(ss[0].equals("z")){
}
}
printTree(tree[0]);
System.out.println();
}
}
public static void printTree(TreeNode root){
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode cur = queue.remove();
if(loop != 1){
System.out.print(cur.val + " ");
}else{
System.out.print(cur.val);
}
loop--;
if(cur.left != null){
queue.add(cur.left);
}
if(cur.right != null){
queue.add(cur.right);
}
}
}
public static class TreeNode{
int val;
TreeNode left, right;
public TreeNode(int val_){
val = val_;
}
}
}