首页 > ACM题库 > 九度OJ > 九度-1078-二叉树遍历[解题代码]
2013
12-12

九度-1078-二叉树遍历[解题代码]

题目来源:2006年清华大学计算机研究生机试真题

题目描述:

二叉树的前序、中序、后序遍历的定义:
前序遍历:对任一子树,先访问跟,然后遍历其左子树,最后遍历其右子树;
中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树;
后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。
给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)。

输入:

两个字符串,其长度n均小于等于26。
第一行为前序遍历,第二行为中序遍历。
二叉树中的结点名称以大写字母表示:A,B,C….最多26个结点。

输出:

输入样例可能有多组,对于每组测试样例,
输出一行,为后序遍历的字符串。

样例输入:
ABC
BAC
FDXEAG
XDEFAG
样例输出:
BCA
XEDGAF

java 代码如下:
import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
	static String str1,str2;
	public static void main(String[] args) {
		Scanner s = new Scanner(new BufferedInputStream(System.in));
		while(s.hasNext()){
			str1 = s.next();
			str2 = s.next();
			Node root = creatTree(str1,str2);
			lastSee(root);
			System.out.println();
		}
		
	}
	
	static void lastSee(Node tree){
		if(tree == null)return;
		lastSee(tree.l);
		lastSee(tree.r);
		System.out.print(tree.data);
	}
	static Node creatTree(String s1,String s2){
		Node n = null;
		if(s1 == null || s2==null)
			return null;
		String left2 = null,right2 = null,news1 = null,news2 = null;
		int len1 = 0;
		char root = s1.charAt(0);
		int index=s2.indexOf(root);
		if(index>0){
			left2 = s2.substring(0,index);
			len1 = left2.length();
		}
		if(index<s2.length()-1)
			right2 = s2.substring(index+1);
		news1 = s1.substring(1, 1+len1);
		news2 = s1.substring(1+len1);
		n = new Node(creatTree(news1,left2),creatTree(news2,right2),s1.charAt(0));
		return n;
	}
}

class Node{
	Node l;
	Node r;
	char data;
	public Node(Node l, Node r, char data) {
		this.l = l;
		this.r = r;
		this.data = data;
	}
	
}

/**************************************************************
	Problem: 1078
	User: coder
	Language: Java
	Result: Accepted
	Time:170 ms
	Memory:15896 kb
****************************************************************/


  1. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。