二叉树前中后序关系

样例哈

       4
     /     \
   1       6
     \     /   \
      3   5     7
      /
    2

前中求后序

先给出样例 节点个数+中序+前序：

7
1 2 3 4 5 6 7 中序
4 1 3 2 6 5 7 前序

输出样例：
2 3 1 5 7 6 4 后序

在这里解释一下下哈：
前序是从根节点开始的，所以前序的第一个数4呢就是根节点，然后在中序里找到4，根据中序的性质（左-->节点-->右）知道，1 2 3为左子树，5 6 7 为右子树，接着从前序下手，1就是根节点之后的左节点，6是根节点之后的右节点，根据这个规律，用递归方法左右节点分别遍历~

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

#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<(b);i++) //虽然看见很多代码都是这么写，感觉会减少一些时间

const int maxN = 35;
int N,M;
struct node{int v;node *lc,*rc;};   //分别为左子树和右子树
int mid[maxN],pre[maxN];

node *build(int *p, int *m, int len){              //每次递归的时候p,m指针都会改变吗？嗯，最终返回根节点
    if(len==0)
      return NULL;              //这里用Dev只允许NULL，nullptr的话会报错 
    node* prt = new node();         //这一步的作用？ 
    prt->v = p[0];                  
    int idx;
    for(idx=0;idx<len;idx++)
        if(m[idx]==p[0])
            break;
    int lsz = idx, rsz = len-idx-1;
    prt->lc = build(p+1,m,lsz);
    prt->rc = build(p+1+lsz,m+idx+1,rsz);            
    return prt;
}

//输出这里不是很明白

void print_path(node *prt){
    if(prt==NULL)
        return;
    print_path(prt->lc);                //每一个prt相当于一个实例，每个节点对应一个实例
    print_path(prt->rc);
    printf("%d ",prt->v);              //因为是后序，所以后面输出
}

int main()
{
    freopen("data.in.txt","r",stdin);
    scanf("%d",&N);
    rep(i,0,N) scanf("%d",&mid[i]);
    rep(i,0,N) scanf("%d",&pre[i]);

    node *prt = build(pre,mid,N);
    print_path(prt);
    return 0;
} 

后中求前序

输入样例 节点个数+中序+后序：

7
1 2 3 4 5 6 7 中序
2 3 1 5 7 6 4 后序

输出样例：
4 1 3 2 6 5 7 嘿嘿，师兄这里错了//逃

按自己理解解释一波：
根据后序的相关性质，4是根节点，从中序中找到根节点，根节点右边为右节点，左边为左节点，再看回后序，6是右节点，1是左节点，然后分为左右子树分别递归啦~

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

#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<(b);i++) 

const int maxN = 35;
int N,M;
struct node{int v;node *lc,*rc;};   //分别为左子树和右子树
//int mid[maxN],pre[maxN];

node *build(int *mid, int *post, int len){
        if(len==0)
        return 0;               
    int idx;
    for(idx=0;idx<len;idx++)
        if(mid[idx]==*(post+len-1))
            break;
    node *rt = new node;
    rt->v = mid[idx];

    rt->lc = build(mid,post,idx);
    rt->rc = build(mid+idx+1,post + idx,len-(idx+1));
    return rt;
}

//两个的输出方式为什么会有区别？ 
void print_tree(node *rt){
    if(rt==NULL)
        return;
    printf("%d ",rt->v);
    print_tree(rt->lc);
    print_tree(rt->rc);

}

int main()
{
    int post[maxN],mid[maxN];
    freopen("data.in.txt","r",stdin);
    scanf("%d",&N);
    rep(i,0,N) scanf("%d",&post[i]);
    rep(i,0,N) scanf("%d",&mid[i]);

    node *rt = build(mid,post,N);
    print_tree(rt);
    return 0;
}