二叉树遍历问题****

Dear 丶 2023-02-23 05:26 21阅读 0赞

我们知道一棵二叉树的遍历方式有三种，分别是先序遍历、中序遍历和后序遍历，我们还知道一棵二叉树的先序遍历和中序遍历可以唯一确定一颗二叉树，同样一棵二叉树的中序遍历和后序序遍历也可以唯一确定一颗二叉树，因此我们可以解决“给定一棵二叉树的先序遍历和中序遍历求解后序遍历”这样的问题，也可以解决“给定一棵二叉树的中序遍历和后序遍历求解先序遍历”这样的问题。经过分析我们知道给定二叉树的先序遍历和后序遍历是不能唯一确定一棵二叉树的！

![在这里插入图片描述][format_png]

上面的图是一颗二叉树，如果仅仅给定先序遍历：ABDCEFG和后序遍历：DBEGFCA，那么除了上面的二叉树以外，还可以是以下三棵二叉树：

![在这里插入图片描述][format_png 1]

![在这里插入图片描述][format_png 2]  
![在这里插入图片描述][format_png 3]

那么如果给定二叉树的先序遍历和后序遍历，到底可能有几棵二叉树呢？

本问题有多组测试数据，第一行是测试数据的组数n，紧接着是n组测试数据。每组测试数据有两行，分别表示二叉树的先序遍历和后序遍历，每个结点用大写字母表示，输入保证数据是正确的。

对于每一组输入，对应的输出只有一行，即符合给定的先序遍历和后序遍历这样条件的二叉树的棵数。

Sample Input

1
    ABDCEFG
    DBEGFCA

Sample Output

代码

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    char a[1010],b[1010];
    int main()
    {
        
        int t;
        scanf("%d",&t);
        while(t--)
        {
        
            scanf("%s%s",a,b);
            int len=strlen(a);
            ll cnt=0;
            for(int i=0;i<len-1;i++)
            {
        
                for(int j=1;j<len;j++)
                {
        
                    if(a[i]==b[j]&&a[i+1]==b[j-1])
                        cnt++;
                }
            }
            cout<<(1ll<<cnt)<<endl;
        }
    }

[format_png]: https://imgconvert.csdnimg.cn/aHR0cDovLzEzOS4xOTYuMTQ1LjkyL2ltYWdlcy9uaXQvJUU0JUJBJThDJUU1JThGJTg5JUU2JUEwJTkxJUU5JTgxJThEJUU1JThFJTg2JUU5JTk3JUFFJUU5JUEyJTk4MS5wbmc?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cDovLzEzOS4xOTYuMTQ1LjkyL2ltYWdlcy9uaXQvJUU0JUJBJThDJUU1JThGJTg5JUU2JUEwJTkxJUU5JTgxJThEJUU1JThFJTg2JUU5JTk3JUFFJUU5JUEyJTk4Mi5wbmc?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cDovLzEzOS4xOTYuMTQ1LjkyL2ltYWdlcy9uaXQvJUU0JUJBJThDJUU1JThGJTg5JUU2JUEwJTkxJUU5JTgxJThEJUU1JThFJTg2JUU5JTk3JUFFJUU5JUEyJTk4My5wbmc?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cDovLzEzOS4xOTYuMTQ1LjkyL2ltYWdlcy9uaXQvJUU0JUJBJThDJUU1JThGJTg5JUU2JUEwJTkxJUU5JTgxJThEJUU1JThFJTg2JUU5JTk3JUFFJUU5JUEyJTk4NC5wbmc?x-oss-process=image/format,png