Java实现 蓝桥杯VIP 算法训练求先序排列

问题描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。

输入格式

　　两行，每行一个字符串，分别表示中序和后序排列

输出格式

　　一个字符串，表示所求先序排列

样例输入

BADC

BDCA

样例输出

ABCD

【分析】根据先序，中序，后序的性质，可以知道：后序的最后一个节点一定是先序的第一个节点；知道了根节点，就可以在中序中分割开左子树和右子树。递归处理左右子树就可以得到先序遍历的结果了。用in，post，pre数组分别表示中序，后序和先序。inStart表示中序的起始位置，inEnd表示中序的终止位置，postIndex表示后序中根节点，preIndex表示要填充的先序的位置。在inStart到inEnd范围内找postIndex位置的根节点，分别求得左子树和右子树的节点个数，确定左子树和右子树在post中的位置，递归求解左子树和右子树。

import java.util.Scanner;

public class 求先序排列 {

	static void makeTree(String mid,String back) {

		char root = back.charAt(back.length()-1);

		System.out.print(root);

		int rootInMid = mid.indexOf(root);

		if(rootInMid > 0){

			makeTree(mid.substring(0,rootInMid),back.substring(0, rootInMid));

		}

		if(rootInMid < mid.length()-1){

			makeTree(mid.substring(rootInMid+1),back.substring(rootInMid,back.length()-1));

		}

	}

	public static void main(String args[]) {

		Scanner input = new Scanner(System.in);

		String mid = input.nextLine();

		String back = input.nextLine();

		makeTree(mid,back);

	}

}