首页 > 试题广场 >

Pre-Post

[编程题]Pre-Post

热度指数：2258 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

We are all familiar with pre-order, in-order and post-order traversals of binary trees. A common problem in data structure classes is to find the pre-order traversal of a binary tree when given the in-order and post-order traversals. Alternatively, you can find the post-order traversal when given the in-order and pre-order. However, in general you cannot determine the in-order traversal of a tree when given its pre-order and post-order traversals. Consider the four binary trees below:

All of these trees have the same pre-order and post-order traversals. This phenomenon is not restricted to binary trees, but holds for general m-ary trees as well.

输入描述:

Input will consist of multiple problem instances. Each instance will consist of a line of the form m s1 s2, indicating that the trees are m-ary trees, s1 is the pre-order traversal and s2 is the post-order traversal.All traversal strings will consist of lowercase alphabetic characters. For all input instances, 1 <= m <= 20 and the length of s1 and s2 will be between 1 and 26 inclusive. If the length of s1 is k (which is the same as the length of s2, of course), the first k letters of the alphabet will be used in the strings. An input line of 0 will terminate the input.

输出描述:

For each problem instance, you should output one line containing the number of possible trees which would result in the pre-order and post-order traversals for the instance. All output values will be within the range of a 32-bit signed integer. For each problem instance, you are guaranteed that there is at least one tree with the given pre-order and post-order traversals.

示例1

输入

2 abc cba
2 abc bca
10 abc bca
13 abejkcfghid jkebfghicda

输出

算法知识视频讲解

Java

two倩

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int m = scanner.nextInt();
if(m==0)
break;
String pre = scanner.next();
String post = scanner.next();
ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
System.out.println(fun(m, pre, post, 1, pre.length() - 1, 0, post.length() - 2, new ArrayList<ArrayList<Integer>>()));
//直接跨过整个数的根结点一个正确的前序和后序前序的第一个结点和后序最后一个相等
}
}

private static long fun(int m, String pre, String post, int pre_start, int pre_end, int post_start, int post_end,ArrayList<ArrayList<Integer>> ret) {
if (post_start > post_end || pre_start > pre_end)//这里说明没有左子树或者右子树返回1（如果返回0，导致递归的乘积为0）
return 1;
//分离出根结点的子树计算有多少个子树
int count = 0;//记录子树个数
long sum = 1;
char pre_root = pre.charAt(pre_start);
char post_root = post.charAt(post_end);
while (pre_start <= pre_end) {//前序序列找子树的根
int i = post_start;
if (pre_root == post_root)//只有一个子树
i = post_end;
//记录子树在前序和后序中的存在位置
for (; i <= post_end; i++) {//后序序列找子树的根
if (pre_root == post.charAt(i)) {
ArrayList<Integer> list = new ArrayList<>();
list.add(pre_start);
list.add(i - post_start + pre_start);
list.add(post_start);
list.add(post_end);
ret.add(list);

count++;//找到了一个子树

//计算下一个子树的位置
pre_start = i - post_start + pre_start + 1;
post_start = i + 1;
if (!(post_start > post_end || pre_start > pre_end))
pre_root = pre.charAt(pre_start);
else
break;
}
}
}
//找完了这个结点的所有子树计算可能的结果
sum *= Fib(count, m);
// 递归遍历子树下的可能性
for (int i = 0; i < ret.size(); i++) {
ArrayList<Integer> list = ret.get(i);
sum *= fun(m, pre, post, list.get(0) + 1, list.get(1), list.get(2), list.get(3) - 1, new ArrayList<ArrayList<Integer>>());
}
return sum;
}
//求Cmn的值
private static long Fib(int n, int m) {
long sum = 1;
for (int i = 0; i < n; i++) {//计算阶乘 Amn
sum *= m;
m--;
}
long div = 1;
for (int i = 1; i <= n; i++) { //计算n的阶乘 Ann
div *= i;
}
//计算Cmn
sum /= div;
return sum;
}
}

发表于 2022-09-17 00:15:56 回复(0)

Java

来学习的小张

import java.util.*;
class SubTree{
    public SubTree(String pre,String post){
        this.pre = pre;
        this.post = post;
    }
    String pre;
    String post;
}
public class Main{
    //计算阶乘
    public static  long fac(int n){
        long f = 1;
        for(int i = 1;i <= n;i++){
            f *= i;
        }
        return f;
    }
    //计算C n m 
    public static long calcCom(int n,int m){
         m = m < (n - m)? m : (n - m);
        long r = 1;
        for(int i = n;i >= n - m + 1;i--){
            r *= i;
        }
        return r / fac(m);
    }
    public static List<SubTree> calcSubTree(String prev,String post){
       //子树的根在前序遍历结果中的位置
        int subRootPreIdx = 1;
        //后序遍历
        int postFirst = 0;
         List<SubTree> subTreeList = new ArrayList<>();
        while(subRootPreIdx < prev.length()){
            //确认该棵子树的根节点
            char rootSub = prev.charAt(subRootPreIdx);
            int subRootPostIdx = post.indexOf(rootSub);
            int subTreeNodeCount = subRootPostIdx - postFirst + 1;
            //从前序和后续遍历结果中分离出该棵子树的前序和后序遍历结果
            SubTree subTree = new SubTree(
                  prev.substring(subRootPreIdx,subRootPreIdx + subTreeNodeCount),
                  post.substring(postFirst,postFirst + subTreeNodeCount)
            );
            subTreeList.add(subTree);
            //继续分离下一棵子树
            subRootPreIdx += subTreeNodeCount;
            postFirst += subTreeNodeCount;
        }
        return subTreeList;
    }
    public static long CalcTreePossible(int m,String pre,String post){
        if(pre.isEmpty() || pre.length() == 1){
            return 1;
        }
        //先分离出根节点有多少棵树
       List<SubTree> subTree =  calcSubTree(pre,post);
        //根节点子树可能性的组合结果
        long result = calcCom(m,subTree.size());
        //根的子树有多少种可能性
        for(SubTree e : subTree){
            result *= CalcTreePossible(m,e.pre,e.post);
        }
        return result;
    }
    public static void main(String[] args){
         Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int m = in.nextInt();
            if(m == 0){
                break;
            }
            //接收子树的前序和后续遍历结果
            String pre = in.next();
            String post = in.next();
            
            System.out.println(CalcTreePossible(m,pre,post));
        }
    }
}

发表于 2022-05-14 19:38:11 回复(0)