题目1078：二叉树遍历（由前序遍历中序遍历得到后序遍历）

痛定思痛。 2021-09-29 13:36 361阅读 0赞

**[题目链接：http://ac.jobdu.com/problem.php?pid=1078][http_ac.jobdu.com_problem.php_pid_1078]**

[**题目详解：https://github.com/zpfbuaa/JobduInCPlusPlus**][https_github.com_zpfbuaa_JobduInCPlusPlus]

通过前序遍历 以及 中序遍历 得到后序遍历

前序遍历可以得到每一层的父节点，然后可以到中序遍历中划分为两个子树。

然后分别对两个子树再次进行相同的操作。

直到左子树为叶子节点

右子树为叶子节点。

因此可以使用自递归算法。

分别找到前序遍历的字符，然后找到字符在中序遍历的位置。

然后将前序遍历以及后续遍历分别划分成两个子树进行上述操作。

最后的返回值为构造的树的根节点即可。

后序遍历，也就是最后输出根节点。

先左后有最后根。打印规则同样适用自递归打印。postOrder

//
    //  1078 二叉树遍历.cpp
    //  Jobdu
    //
    //  Created by PengFei_Zheng on 09/04/2017.
    //  Copyright © 2017 PengFei_Zheng. All rights reserved.
    //
     
    #include <stdio.h>
    #include <iostream>
    #include <algorithm>
    #include <string.h>
     
    using namespace std;
     
    struct Node{
        Node *lchild;
        Node *rchild;
        char c;
    }tree[50];
     
    int loc;
    Node *creat(){
        tree[loc].lchild=tree[loc].rchild=NULL;
        return &tree[loc++];
    }
     
    char str1[30], str2[30];
    void postOrder(Node *T){
        if(T->lchild!=NULL)
            postOrder(T->lchild);
        if(T->rchild!=NULL)
            postOrder(T->rchild);
        printf("%c",T->c);
    }
     
    Node *build(int s1, int e1, int s2, int e2){
        Node* ret = creat();
        ret->c=str1[s1];
        int rootIdx=0;
        for(int i = s2 ; i <=e2 ;  i++){
            if(str2[i] == str1[s1]){
                rootIdx=i;
                break;
            }
        }
        if(rootIdx!=s2){
            ret->lchild=build(s1+1, s1+(rootIdx-s2), s2, rootIdx-1);
        }
        if(rootIdx!=e2){
            ret->rchild=build(s1+(rootIdx-s2)+1, e1, rootIdx+1, e2);
        }
        return ret;
    }
     
    int main(){
        while(scanf("%s",str1)!=EOF){
            scanf("%s",str2);
            loc=0;
            int l1 = (int)strlen(str1);
            int l2 = (int)strlen(str2);
            Node* T = build(0,l1-1,0,l2-1);
            postOrder(T);
            printf("\n");
        }
        return 0;
    }
     
    /**************************************************************
        Problem: 1078
        User: zpfbuaa
        Language: C++
        Result: Accepted
        Time:0 ms
        Memory:1520 kb
    ****************************************************************/

转载于:https://www.cnblogs.com/zpfbuaa/p/6684057.html

[http_ac.jobdu.com_problem.php_pid_1078]: http://ac.jobdu.com/problem.php?pid=1078
[https_github.com_zpfbuaa_JobduInCPlusPlus]: https://github.com/zpfbuaa/JobduInCPlusPlus