二叉树的后序遍历（二叉树）

1.题目：

Problem Description

给你一个二叉树的前序遍历和中序遍历，输出这个二叉树的后序遍历。

Input

输入数据有多组，每组占三行：

第一行为一个整数n（n<=100），表示这个二叉树的节点个数，节点数据类型为整型。

第二行有n个数，表示二叉树的前序遍历序列，各节点值之间有一空格。

第三行有n个数，表示二叉树的中序遍历，各节点值之间有一空。

Output

对于每组数据，输出二叉树的后序遍历，元素之间用一个空格分隔，每组输出占一行。

Sample Input

9
1 2 4 7 3 5 8 9 6
4 7 2 1 8 5 9 3 6
      

Sample Output

7 4 2 8 9 5 6 3 1
      

2.代码一：

#include <iostream>
using namespace std;

struct BiNode {
    int data;
    struct BiNode* left, *right;
};

int n;
void BiOrder(int* pre, int* mid, int len);

int main()
{
    int i, j, pre[101], mid[101];

    while (~scanf("%d", &n)) {

        for (i = 0; i < n; i++)
            scanf("%d ", &pre[i]);  ///从键盘上接收前序序列

        for (j = 0; j < n; j++)
            scanf("%d ", &mid[j]);  ///从键盘上接收中序序列

        BiOrder(pre, mid, n); ///调用操作，输出后序序列

        printf("\n");
    }

    return 0;
}

void BiOrder(int* pre, int* mid, int len)
{
    if (len <= 0)
        return ;    ///如果长度为非正数的，就结束
    BiNode* p = new BiNode;  ///动态生成一个节点p
    p->data = *pre; ///并将该结点指向前序序列
    int i;
    for (i = 0; i < len; i++) { ///遍历中序序列
        if (mid[i] == *pre)
            break;    ///在中序序列中找到根节点的位置
    }
    BiOrder(pre + 1, mid, i); ///递归遍历左子树
    BiOrder(pre + i + 1, mid + i + 1, len - (i + 1)); ///递归遍历右子树
    if (len < n)
        printf("%d ", p->data);
    else
        printf("%d", p->data);
}
           

 代码二：

#include <stdio.h>
#include <string.h>

struct TreeNode {
    int date;
    struct TreeNode* left;
    struct TreeNode* right;
};

int n;

void BiOrder(int* mid, int* pre, int len)
{
    if (len <= 0) //是退出这个函数的条件
        return ;
        
    TreeNode* node = new TreeNode;
    
    node->date = *pre;
    
    int i = 0;
    
    for (; i < len; i++) {
        if (mid[i] == *pre)
            break;
    }//这个就是找到中序历遍中和前序历遍第一个数相等的数
    
    BiOrder(mid, pre + 1, i);
    BiOrder(mid + i + 1, pre + i + 1, len - (i + 1));
    /*比如pre={1,2,4,5,3}   mid={4,2,5,1,3}  那么我们先找到1,然后1把mid分成两部分{4,2,5} 和{3}
       pre从2开始长度为3的就是左子树的前序历遍，mid的左半部分三个就是左子树的后续历遍，所以继续递归*/
       
    if (len < n)
        printf("%d ", node->date);
    else
        printf("%d", node->date);
    /*前n-1个数，输出的时候后边都加上一个空格，最后一个不加，就能弄成题目要求的输出格式了*/
    
    return ;
}

int main()
{
    int i, j, pre[101], mid[101];
    
    while (~scanf("%d", &n)) {
            
        for (i = 0; i < n; i++)
            scanf("%d ", &pre[i]);
    
        for (j = 0; j < n; j++)
            scanf("%d ", &mid[j]);
            
        BiOrder(mid, pre, n);
        
        printf("\n");
    }
    
    return 0;
}