HDU1622 Java
时间: 2024-02-23 19:53:33 浏览: 29
根据提供的引用内容,这是一道关于二叉树的问题,需要输出每个二叉树的层序遍历。如果二叉树没有完全给出,则输出“not complete”。而且,这道题目是一个ACM竞赛的题目,需要使用Java语言进行编写。
以下是Java语言的代码实现:
```java
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String s = sc.nextLine();
if (s.equals("")) {
continue;
}
String[] arr = s.split(" ");
int len = arr.length;
int[] tree = new int[len];
boolean[] flag = new boolean[len];
for (int i = 0; i < len; i++) {
if (arr[i].equals("()")) {
tree[i] = -1;
flag[i] = true;
} else {
tree[i] = Integer.parseInt(arr[i].substring(1, arr[i].length() - 1));
}
}
int root = 0;
for (int i = 0; i < len; i++) {
if (!flag[i]) {
root = i; break;
}
}
boolean isComplete = true;
Queue<Integer> queue = new LinkedList<>();
queue.offer(root);
int index = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int cur = queue.poll();
if (tree[cur] == -1) {
if (index < len && !flag[index]) {
isComplete = false;
}
} else {
if (cur * 2 + 1 < len) {
queue.offer(cur * 2 + 1);
if (tree[cur * 2 + 1] != -1) {
flag[cur * 2 + 1] = true;
}
}
if (cur * 2 + 2 < len) {
queue.offer(cur * 2 + 2);
if (tree[cur * 2 + 2] != -1) {
flag[cur * 2 + 2] = true;
}
}
}
index++;
}
}
if (!isComplete) {
System.out.println("not complete");
continue;
}
queue.offer(root);
StringBuilder sb = new StringBuilder();
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int cur = queue.poll();
sb.append(tree[cur]).append(" ");
if (cur * 2 + 1 < len && tree[cur * 2 + 1] != -1) {
queue.offer(cur * 2 + 1);
}
if (cur * 2 + 2 < len && tree[cur * 2 + 2] != -1) {
queue.offer(cur * 2 + 2);
}
}
}
System.out.println(sb.toString().trim());
}
}
}
```