题解 | #二叉树遍历#

//利用先序和中序重新构造树，构造完成后后序遍历即可。其中对树的构造可采用分治递归的思想
#include "stdio.h"
#include "string"
using namespace std;
struct TreeNode{
    char data;
    TreeNode *leftChild;
    TreeNode *rightChild;
};

TreeNode *RebuildTree(string PreOrder,string Inorder){//利用先序和中序重新构造树
    if (PreOrder.size()==0)
        return NULL;
    else{
        TreeNode *node = new TreeNode;//建在堆中
        node->data=PreOrder[0];
        char N = PreOrder[0];
        int pos = Inorder.find(N);
        node->leftChild = RebuildTree(PreOrder.substr(1,pos),Inorder.substr(0,pos));
        node->rightChild = RebuildTree(PreOrder.substr(pos+1),Inorder.substr(pos+1));
        return node;
    }
}

void PostOrder(TreeNode *node){
    if (node!=NULL){
        PostOrder(node->leftChild);
        PostOrder(node->rightChild);
        printf("%c",node->data);
    }
    return;
}

int main(){
    char PreOrder[30];
    char InOrder[30];
    while (scanf("%s%s",PreOrder,InOrder)!=EOF){
        TreeNode *root = RebuildTree(PreOrder,InOrder);
        PostOrder(root);
        printf("\n");
    }
}