Java解 PATA1020 Tree Traversals

题目描述

1020 Tree Traversals （25 分）

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.

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 postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the level order traversal sequence of the corresponding binary tree. 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:

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

Sample Output:

4 1 6 3 5 7 2

代码

先序、后序、层次遍历序列分别和中序序列都可以构造出一个完整的序列。而如果没有中序序列就无法构造，因为无法判断根节点的位置。

后序遍历最后一个数w一定为根节点，因为每一个节点的var值不同，所以可以遍历中序序列，找到等于w的值，那么w前面的数都属于w节点的左子树中的节点的var值，w后面的数都属于w节点右子树中的值。

用【pL，pR】表示后序遍历区间，用【inL，inR】表示中序遍历区间，以上述的思路对树进行后序遍历，直到区间长度为0。
使用样例来说明

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main{

	static int n;
	static int [] post=new int[35];//后序遍历序列
	static int [] in=new int[35];//中序遍历序列
	static class Node{
		int var; 
		Node left;
		Node right;
	}
	static Node create(int pL,int pR,int inL,int inR) {
		if(pL>pR) return null; 
		Node root=new Node();
		int var=post[pR];
		root.var=var;
		int k=inL;
		for(;k<=inR;k++) {
			if(in[k]==post[pR]) break;
		}
		int num=k-inL;
		root.left=create(pL,pL+num-1,inL,k-1);
		root.right=create(pL+num,pR-1,k+1,inR);
		return root;
	}
	static void bfs(Node root) {
		Queue<Node> q=new LinkedList<Node>();
		q.add(root);
		int i=0;
		while(!q.isEmpty()) {
			Node p=q.remove();
			if(i!=n-1){
			  System.out.print(p.var+" ");  
			}else{
			  System.out.print(p.var);
			}
			i++;
			if(p.left!=null) {
				q.add(p.left);
			}
			if(p.right!=null) {
				q.add(p.right);
			}
			
		}
	}
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		n=Integer.parseInt(br.readLine());
		String[] token1=br.readLine().split(" ");
		String[] token2=br.readLine().split(" ");
		for(int i=0;i<n;i++) {
			post[i]=Integer.parseInt(token1[i]);
			in[i]=Integer.parseInt(token2[i]);
		}
		Node root=create(0,n-1,0,n-1);
		bfs(root);
	}

}

在bfs进行层次遍历时，要注意这里使用LinkedList即根据入队顺序出队。如果使用PriorityQueue队列用例并不能全部通过。