题目描述

众所周知，遍历一棵二叉树就是按某条搜索路径巡访其中每个结点，使得每个结点均被访问一次，而且仅被访问一次。最常使用的有三种遍历的方式：

１．前序遍历：若二叉树为空，则空操作；否则先访问根结点，接着前序遍历左子树，最后再前序遍历右子树。

２．中序遍历：若二叉树为空，则空操作；否则先中序遍历左子树，接着访问根结点，最后再前中遍历右子树。

３．后序遍历：若二叉树为空，则空操作；否则先后序遍历左子树，接着后序遍历右子树，最后再访问根结点。

现在的问题是给定前序遍历和后序遍历的顺序，要求出总共有多少棵不同形态的二叉树满足这样的遍历顺序。

输入描述

输入有多组数据，每组数据两行，第一行给出前序遍历的访问顺序，第二行给出后序遍历的访问顺序。
二叉树的结点用一个大写字母表示，不会有两个结点标上相同字母。输入数据不包含空格，且保证至少有一棵二叉树符合要求。
输出一个整数，为符合要求的不同形态二叉树的数目。

样例输入
ABCD
CBDA
样例输出
2

源码：

import java.util.Scanner;

public class Main {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            String a=scanner.next();//用于存放先序遍历结果
            String b=scanner.next();//用于存放后序遍历结果
            int count=0;
            for(int i=0;i<a.length()-1;i++) {
                for(int j=b.length()-1;j>=1;j--) {
                    if (a.charAt(i)==b.charAt(j)&&a.charAt(i+1)==b.charAt(j-1)) {
                        count++;
                    }
                }
            }
            int n=(int) Math.pow(2, count);
            System.out.println(n);
        }
    }

总结：
使中序遍历产生摇摆的原因，在于含有一个孩子结点的结点个数，因此，只需要统计仅含有一个孩子结点的结点个数即可。如何在前序遍历和中序遍历中寻找只含一个孩子的结点？ 只要前序序列中含有AB，而后序遍历含有BA，则说明A为仅含有一个孩子的结点，B为A的孩子。因此，只要统计出这样的结点个数，即可求解。