PAT A1086 Tree Traversals Again [二叉树前序中序求后序]

题目描述

链接
用栈的形式给出一棵二叉树的建立的顺序，求这棵二叉树的后序遍历

分析

• 性质：树的先序等于入栈次序，树的中序遍历等于出栈次序
  • 先序：先访问根再入栈，所以入栈次序就是先序遍历次序
  • 中序：先递归访问左子树，回溯时访问根，回溯时即出栈时，所以出栈次序就是中序遍历
• 所以问题转换为已知先序中序，求后序
• 已知先序中序求后序的方法
  • (root) 保存先序中根的位置，(st)，(ed) 为中序子树的起始结束位置
  • 遍历中序，找到中序根的位置(i)，从而分成左右子树
  • 左子树在先序中根的位置(root+1) ，右子树在先序中根的位置(root+左子树结点数)
  • 在中序中找左子树结点数(i-st+1) ，右子树根位置:(root+i-st+1)
  • 求后序：就是先左右递归dfs，再访问根

void dfs(int root, int st, int ed){
	if(st > ed) return; //中序长度小于等于0
    int i = st;
    while(i<=st&&in[i]!=pre[root]) i++;
    dfs(root+1, st, i-1);
    dfs(root+i-st+1, i+1, ed);
    ans.push_back(pre[root]);
}

• 求层序遍历：
  • 加一个变量(index) ，表示当前根结点在二叉树中所对应的下标（从0开始），左子树(2*index+1) ,右子树(2*index+2) (因为下标从0开始，不是从1开始)
  • 输出先序的递归的时候，把节点的(index)和(value)放进结构体里，再装进(vector)里
  • 在递归完成后，(vector)中按照(index)排序就是层序遍历的顺序

struct node {
    int index, value;
};
bool cmp(node a, node b) {
    return a.index < b.index;
}
vector<int> post, in;
vector<node> ans;
void dfs(int root, int st, int ed, int idx) {
    if (st > ed) return;
    int i = st;
    while (i <= end && in[i] != post[root]) i++;
    ans.push_back({idx, post[root]});
    dfs(root - 1 - ed + i, st, i - 1, 2 * idx + 1);
    dfs(root - 1, i + 1, ed, 2 * idx + 2);
}
pre(n - 1, 0, n - 1, 0);
sort(ans.begin(), ans.end(), cmp);

• 为了避免树中多个值相同，会出问题，故先序，中序后序都保存的是(key) ，用(value) 保存实际的值

完整代码

#include<bits/stdc++.h>
using namespace std;

vector<int> pre, in, post, value;
stack<int> s;
int n,num,key;
char str[10];
//先序对应入栈，中序对应出栈
//一直先序，中序，求后序
void dfs(int root, int st, int ed){
    if(st > ed) return;
    int i = st;
    while(i<=ed && in[i] != pre[root]) i++;
    //左右根
    dfs(root+1, st, i-1);
    dfs(root+(i-st+1), i+1, ed);
    post.push_back(pre[root]);
}
int main(){
    scanf("%d",&n);
    while(~scanf("%s", str)){
        if(strlen(str) == 4){
            scanf("%d",&num);
            pre.push_back(key); //前中后序均保存key,避免值相同而出现问题
            value.push_back(num);
            s.push(key++);
        }else{
            in.push_back(s.top());
            s.pop();
        }
    }
    dfs(0, 0, n-1);
    for(int i=0;i<post.size();i++){
        if(i==0) printf("%d",value[post[i]]);
        else printf(" %d",value[post[i]]);
    }
    printf("
");

}