7-2 树的遍历 (PTA-数据结构)_树的遍历pta

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例：

4 1 6 3 5 7 2

---

提交结果： 

---

思路分析：

        面对该题，博主起初打算根据上一题（根据后序和中序遍历输出先序遍历）的思路，先设置一个用数组存储的先序遍历结果，再通过某些数学关系，用先序遍历来找出层序遍历，后来发现似乎没有必要联系，便退回到起初，打算类同于在后序和中序遍历中创建二叉链表储存的树。

        第一个版本：因为之前已经有后序和中序得到先序的代码，所以打算用先序来创建一棵二叉树，如下：

void makePre(int Tree[], int post[], int min[], int root, int fin, int start){
    if((fin <= start)||(root<0)) {
        return;
    }
    int i;
    int head = post[root];
    Tree[flag] = head;
    flag++;
    for(i=start; i<fin;i++) {
        if (min[i] == head) {
            break;
        }
    }
    makePre(Tree,post,min,root-fin+i,i,start);
    makePre(Tree,post,min,root-1,fin,i+1);
}
 
TreeNode* buildTree(int preorder[], int start, int end) {
    if (start > end) {
        return NULL;
    }
 
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = preorder[start];
 
    int i = start + 1;
    while (i <= end && preorder[i] < root->val) {
        i++;
    }
 
    root->left = buildTree(preorder, start + 1, i - 1);
    root->right = buildTree(preorder, i, end);
 
    return root;
}
void LevelOrder(TreeNode *root, int num)     //二叉树的层次遍历
{
    TreeNode *temp[100000];                   //创建pTreeNode指针类型的指针数组(真想不出来)
    int in = 0;
    int out = 0;
 
    temp[in++] = root;                      //先保存二叉树根节点
    int n = 0;
    while (in > out)
    {
        if (temp[out])
        {
            if(n == num-1)
                printf("%d",temp[out]->val);
            else printf("%d ",temp[out]->val);
            temp[in++] = temp[out]->left;
            temp[in++] = temp[out]->right;
            n++;
        }
        out++;
    }
}

（固定且有效的算法）

        先序创建二叉树buildTree：此算法是根据结点的值来判定左右子树的，因此其中的循环判断第一个大于根节点的值再去进行下面的遍历，从而继续创建左右子树（可能是造成此种思路失败原因）；

        LevelOrder层序遍历：使用了队列来储存正在遍历的结点，之后若不空，打印其值，并再将其左右孩子入队，做到一层一层的打印出来值。

        但是在上面思路的这种情况下，pta最后一个检查点无法通过，找不到bug的存在，因此只得求助于其他博客，我得到了用中序和后序直接创建树的代码，进行了二次尝试：

TreeNode* buildTree(int min[], int post[], int n){
    if(!n)
        return NULL;
    TreeNode *T = (TreeNode *)malloc(sizeof(struct TreeNode));
    T->val = post[n-1];            //后序遍历的最后一个节点就是树的根节点
    T->left = T->right = NULL;
 
    //从中序遍历中找到根节点的位置
    int index;
    for(index=0; index<n; index++) {
        if(min[index] == post[n-1]) break;
    }
 
    T->left = buildTree(min, post, index);
    T->right = buildTree(min+index+1, post+index, n-index-1);
    return T;
}

        中序后序创建树：该代码算法思想和上面我们提到用后序和中序创建树的思想很像，具体再递归传参，但是此算法直接通过偏移量传数组，上面makePre函数则是通过了两个int型变量存下标，但是区别不大。之后将该代码段替换掉我上面创建先序遍历数组，和通过先序数组创建树的代码，成功解决问题，没有错误通过。

---

代码内容：

//
// Created by DDD on 2023/11/20.
//
#include <stdio.h>
#include <malloc.h>
 
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;
 
TreeNode* buildTree(int min[], int post[], int n){
    if(!n)
        return NULL;
    TreeNode *T = (TreeNode *)malloc(sizeof(struct TreeNode));
    T->val = post[n-1];            //后序遍历的最后一个节点就是树的根节点
    T->left = T->right = NULL;
 
    //从中序遍历中找到根节点的位置
    int index;
    for(index=0; index<n; index++)
    {
        if(min[index] == post[n-1]) break;
    }
    T->left = buildTree(min, post, index);
    T->right = buildTree(min+index+1, post+index, n-index-1);
    return T;
 
}
 
 
void LevelOrder(TreeNode *T)
{
    if(T)
    {
        TreeNode *queue[100];
        int left = 0, right = 0;
        queue[right++] = T;
        while (left < right)
        {
            TreeNode *bt = queue[left++];
            if(bt == T)
                printf("%d", bt->val); //为根节点时，无空格输出
            else
                printf(" %d", bt->val);
            if(bt->left)
                queue[right++] = bt->left;
            if(bt->right)
                queue[right++] = bt->right;
        }
    }
}
 
 
int main(){
    int num;
    scanf("%d",&num);
    int post[100];                      //后序
    int min[100];                       //中序
    //int Tree[1000] = {0};               //先序
    for(int i=0; i<num;i++){
        scanf("%d",&post[i]);
    }
    for(int i=0; i<num;i++){
        scanf("%d",&min[i]);
    }
    //makePre(Tree,post,min,num - 1,num,0);
    TreeNode TN = *buildTree(min,post,num);
    LevelOrder(&TN);
}

---

后记：

        总而言之，树往后的需要我们掌握的固定算法太多，还需要我们去亲手写一下，走走代码的整个思路。难度突然就上来了。

---

return 0;//载酒买花少年事