Sicily 1210. Binary Tree

Posted on | In | |

题目描述

在众多的数据结构中，二叉树是一种特殊而重要的结构，有着广泛的应用。二叉树或者是一个结点，或者有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。

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

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

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

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

对一棵二叉树，如果给出前序遍历和中许遍历的结点访问顺序，那么后序遍历的顺序是唯一确定的，也很方便地求出来。但如果现在只知道前序遍历和后序遍历的顺序，中序遍历的顺序是不确定的，例如：前序遍历的顺序是ABCD，而后序遍历的顺序是CBDA，那么就有两课二叉树满足这样的顺序（见图(1)和图(2)）。

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

Input

整个输入有两行，第一行给出前序遍历的访问顺序，第二行给出后序遍历的访问顺序。

二叉树的结点用一个大写字母表示，不会有两个结点标上相同字母。输入数据不包含空格，且保证至少有一棵二叉树符合要求。

Output

输出一个整数，为符合要求的不同形态二叉树的数目。

Sample Input

ABCD
CBDA

Sample Output

2

算法分析

首先思考：什么样的两棵不同二叉树，会有相同的先序遍历和后序遍历呢？

根据中序遍历和先序遍历，或者根据中序遍历和后序遍历，都能够确定唯一的一棵二叉树，但是只根据先序遍历和后序遍历，是无法达到这个目的的。

原因如下：
先序遍历和后序遍历有一个共同的缺点，即无法确定一个子结点，是它的父结点的左儿子还是右儿子。

例如：

A 　　　　A
/　　　　　\
B　　　　　B
\　　　　　／
C　　　　 C

以上两棵二叉树，结构明显不同，但是先序遍历都是ABC，后序遍历都是CBA。而只有通过中序遍历，才能找到两者的区别：前者是BCA，后者是ACB。而在先序和后序遍历结果相同的情况下，导致结构差异产生的，便是子树所在的左/右方向不同。

那么，原问题就可以转化为：根据先序和后序遍历，求这样的二叉树中只有一个子树的结点的个数n，那么，2的n次方即是不同形态的二叉树的数量。

接下来，要用简单的方法解出这道题，首先要弄清楚先序遍历和后序遍历的规律。

以题目中的先序ABCD，后序CBDA为例，先序遍历的第一个结点A，以及后序遍历的最后一个结点A，必定是整棵二叉树的根结点。先序遍历中，根结点的后一位B，一定是A的子结点，但暂时无法确定是左子树还是右子树，只能根据先序遍历的顺序暂时默认为左子树。后序遍历中，根结点的前一位D，也一定是A的子结点，那么默认为A的右子树。显然，B、D分别是A的左、右子结点，A并不是我们想找的只有一个子树的父结点。只有当先序中A的后一位，与后序中A的前一位相同时，可以确定，A只有一个子树。

代码实现

根据这种规律，可以写出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int main() {
    string pre;
    string post;
    cin >> pre >> post;
    int counter = 0;
    // 遍历先序中的每一个结点
    for (int i = 0; i < pre.length(); i++)
        for (int j = post.length() - 1; j >= 0; j--)
        // 对于先序中的每一个结点，在后序中找到
            if (pre[i] == post[j]) {
                if (i != pre.length() - 1 && j != 0 && pre[i + 1] == post[j - 1])
            // 先序中该结点的后一位，与后序中该结点的前一位相同时，计数器++
                    counter++;
                break;
            }
    int answer = pow(2, counter);
    cout << answer << endl;
    return 0;
}

本文为博主原创文章，转载请注明出处。