PAT 1020 1119 洛谷1229 二叉树的遍历、递归与分治

知识复习

先说结论

根据前序中序可以唯一确定后序或者层序

根据后序中序可以唯一确定前序或者层序

当二叉树的每个节点都不会只有一个孩子时，根据前序后序可以唯一确定中序或者层序

上述确定过程不需要实际建树

二叉树的三种遍历

首先二叉树的前中后序遍历，分别是“根左右”，“左根右”和“左右根”，这一点是最基础的。但是这里的左右，不仅指的是左孩子和右孩子，还指的是左子树和右子树，它们在根节点确定的时候是集中在一起的，例如：

前序：(根)[左子树][右子树]
中序：[左子树](根)[右子树]
后序：[左子树][右子树](根)

它们的结构都是递归的，因此在具体实现的时候，都采用一种类似分治的递归方式去实现，两个递归函数和一个根相关语句的相对顺序刚好就对应着不同的遍历方式。

根据中序和其它一种遍历顺序确定另一种

根据上面的结构，我们可以根据中序和其它一种遍历确定另一种。例如前序和中序，首先整个前序序列的第一个元素一定是根节点，拿着这个节点在中序中找到其位置就可以确定左右子树，相应的，根据中序确定的左子树的长度，可以确定前序中左右子树的长度，因为它们仍然是集中在一起的。上述过程又可以对左右子树进行递归，直到只有一个叶节点。类似分治的常用模板。

后中->前：

#include <cstdio>
using namespace std;
int post[] = {3, 4, 2, 6, 5, 1};
int in[] = {3, 2, 4, 1, 6, 5};
// 根据后中确定前
void pre(int root, int start, int end) {
    if(start > end) return;
    // 确定中序中根节点的位置
    int i = start;
    for(;i <= end;i++){
        if(in[i] == post[root]){
            break;
        }
    }
    // 前序遍历，先输出根节点
    printf("%d ",post[root]);
    pre(root-1-end+i, start, i-1);
    pre(root-1, i+1, end);
}
 
int main() {
    pre(5, 0, 5);
    return 0;
}

PAT1020在此基础上，每次记录所在层数，并用队列输出即可，代码如下：

#include <cstdio>
#include <string.h>
#include <queue>
using namespace std;

int N,po[50],in[50];

queue<int> le[50];

void level(int root,int left,int right,int pos){// pos代表第几层
    if(left > right) return;
    // 确定中序的这个子树中根节点的位置
    int i = left;
    for(;i <= right;i++){
        if(po[root] == in[i]) break;
    }
    // 记录根节点在层序中的位置
    le[pos].push(po[root]);
    
    // 将该子树分为左右两个子树
    level(root - 1 - right + i, left, i - 1, pos + 1);
    level(root - 1, i + 1, right, pos + 1);
}

int main(){
    scanf("%d",&N);
    for(int i = 0;i < N;i++)
        scanf("%d",&po[i]);
        
    for(int i = 0;i < N;i++)
        scanf("%d",&in[i]);

    level(N-1, 0, N-1, 0);

    int j = 0;
    while(!le[j+1].empty()){
        while (!le[j].empty()) {
            printf("%d ",le[j].front());
            le[j].pop();
        }
        j++;
    }
    while (le[j].size()!=1) {
        printf("%d ",le[j].front());
        le[j].pop();
    }
    printf("%d",le[j].front());
}

6ms

根据前序后序确定中序

基本思路应该还是类似的，根据前序的特点，第一个节点是整个子树的根节点，这个节点后面的节点应该是左子树的根节点，如下：

前序：(根)[(根)左子树][右子树]
后序：[左子树(根)][右子树](根)

因此确定了前序左子树的根后，在后续中找到对应的位置，就可以确定左右子树了，按照和前面类似的思路递归即可。

但是为什么说无法唯一确定呢？原因在于有一种情况如下：

前序：(根)[(根)左子树]
后序：[左子树(根)](根)

这个时候后序左子树的根刚好是倒数第二个，只有一个子树，你是分不清左右的，这个子树既可以是左子树，又可以是右子树，因此就具有二义性了。而中序由于可以根据根左右来判断是哪个子树，所以是没有问题的。

因此在确定的时候，随便选左子树还是右子树就可以了。

PAT1119就是这个问题，代码如下：

#include <cstdio>
#include <queue>
#include <iostream>
using namespace std;

int N,po[50],pre[50];

bool flg = true;
queue<int> res;

void in(int root,int left,int right){
    if(left > right) return;
    // 确定前序的根的下一个在这个子树中的位置
    int i = left;
    for(;i < right;i++){
        if(pre[root+1] == po[i]) break;
    }
    
    // 一个子树都没有
    if(i==right){
        //printf("%d ",pre[root]);
        res.push(pre[root]);
    }
    // 仅有一个子树
    else if(i==right-1){
        // 默认为左子树
        in(root+1,left,right-1);
        res.push(pre[root]);
        // 默认为右子树
        //in(root+1,left,right-1);
        flg = false;
        //printf("%d ",pre[root]);
    }
    // 两个子树都在
    else if(i!=right-1){
        in(root+1,left,i);
        //printf("%d ",pre[root]);
        res.push(pre[root]);
        in(root+i-left+2,i+1,right-1);
    }
}

int main(){
    scanf("%d",&N);
    for(int i = 0;i < N;i++)
        scanf("%d",&pre[i]);
        
    for(int i = 0;i < N;i++)
        scanf("%d",&po[i]);
    in(0, 0, N-1);
    printf(flg?"Yes\n":"No\n");
    while (res.size()!=1) {
        printf("%d ",res.front());
        res.pop();
    }
    printf("%d\n",res.front());
}

6ms

由前序和后序遍历所确定的二叉树数量

根据刚才的分析，我们可以知道，当满足：a[i]==b[j]且a[i+1]==b[j-1]时，就有一个只有一个子树的节点。因此，统计所有的这种点，就可以得到总数。

洛谷1229就是这个问题，代码如下：

#include <iostream>
#include <string>
#include <math.h>
using namespace std;

int main(){
    string a,b;
    cin>>a>>b;
    long long cnt = 0;
    
    for(int i = 0;i < a.length()-1;i++){
        for(int j = 1;j < b.length();j++){
            if(a[i]==b[j] && a[i+1]==b[j-1]){
                cnt++;
            }
        }
    }
    
    cout<<pow(2,cnt);
}

2ms

以上所有树每个节点都是独一无二的。