# ZigZagging on a Tree二叉树蛇形层次遍历（Java语言）

### 题目描述：

Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences. And it is a simple standard routine to print the numbers in level-order. However, if you think the problem is too simple, then you are too naive. This time you are supposed to print the numbers in “zigzagging order” – that is, starting from the root, print the numbers level-by-level, alternating between left to right and right to left. For example, for the following tree you must output: 1 11 5 8 17 12 20 15.

### Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the inorder sequence and the third line gives the postorder sequence. All the numbers in a line are separated by a space.

### Output Specification:

For each test case, print the zigzagging sequence of the tree in a line. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

8
12 11 20 17 1 15 8 5
12 20 17 11 15 8 5 1


Sample Output:

1 11 5 8 17 12 20 15

### 代码：

package text_9_25;

import java.util.ArrayList;
import java.util.Queue;
import java.util.Scanner;

public class ZigZaggingOnATree {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int in[] = new int[n];
int post[] = new int[n];
for(int i=0;i<n;i++)
in[i] = scanner.nextInt();
for(int i=0;i<n;i++)
post[i] = scanner.nextInt();
//创建二叉树
Node root = BuildTree(in, 0, n-1, post, 0, n-1);

//蛇形层次遍历
PrintLevelOrder(root);

}

public static Node BuildTree(int in[],int ibegin,int iend,int post[],int pbegin,int pend) {
if(ibegin>iend||pbegin>pend) return null;
Node root = new Node(post[pend]);
for(int i=ibegin;i<=iend;i++) {
if(post[pend]==in[i]) {
root.left = BuildTree(in, ibegin, i-1, post, pbegin, pbegin-ibegin+i-1);
root.right = BuildTree(in, i+1, iend, post, pbegin-ibegin+i, pend-1);
}
}
return root;
}
public static void PrintLevelOrder(Node root) {
boolean reversed = false;//反转标志
int flag=1;//用于输出格式控制
while(!queue.isEmpty()) {
int size = queue.size();//当前层的节点数
for(int i=0;i<size;i++) {  //对应每一层
Node temp = queue.poll();

}
//      System.out.println(size);
if(flag==1) {
flag=0;
}
}
reversed =!reversed;  //每次反转
}
}

}
class Node{   //树节点类
public int data;
public Node left;
public Node right;
public Node(int data){
this.data = data;
left = right = null;
}
}



|
6天前
|

Java语言使用DL4J实现图片分类
【6月更文挑战第14天】Java语言使用DL4J实现图片分类
18 3
|
3天前
|

【算法】重建二叉树并进行后序遍历的Java实现
【算法】重建二叉树并进行后序遍历的Java实现
14 5
|
2天前
|
Java 数据安全/隐私保护 开发者
Java是一种完全支持面向对象编程的语言，其面向对象特性包括封装、继承、多态和抽象等
【6月更文挑战第18天】**面向对象编程（OOP）通过对象封装状态和行为，实现问题域的抽象。Java全面支持OOP，核心特性包括**： - **封装**：保护数据安全，隐藏内部细节。 - **继承**：子类继承父类属性和行为，促进代码重用。 - **多态**：一个接口多种实现，增强灵活性和扩展性。 - **抽象**：通过接口和抽象类抽离共性，简化复杂性。 **Java的OOP便于理解和解决复杂系统问题。**
13 3
|
1天前
|

8 1
|
9天前
|

Java一分钟之-GraphQL：查询语言与API设计
20 2
|
12天前
|

Python vs. Java：语言之争的终结
【6月更文挑战第8天】Python与Java，两种影响力巨大的编程语言，各有千秋。Python以简洁语法和强大库支持在数据科学、机器学习领域大放异彩，适合快速原型设计；而Java以其稳定性能、跨平台兼容性在大型系统、企业应用中占据一席之地。语言之争实为互补，开发者应根据项目需求选择合适工具，两者和谐共存，共同推动编程技术进步。
15 1
|
13天前
|

Java语言中反射动态代理接口的解释与演示
Java语言中反射动态代理接口的解释与演示
9 1
|
2天前
|
Java 大数据 API
|
6天前
|
IDE Oracle Java
[笔记] 疯狂JAVA讲义（第3版） 第1章 Java语言概述与开发环境
[笔记] 疯狂JAVA讲义（第3版） 第1章 Java语言概述与开发环境
16 0
|
7天前
|
Java

3 0