题解 | #二叉树遍历#

#include <string>
using namespace std;
struct TreeNode{
    char data;
    TreeNode * leftChild;
    TreeNode * rightChild;
};
TreeNode * rebuild(string preorder,string inorder){
        //返回子树根节点的地址
    if (preorder.size() == 0){
        return NULL;
    } else{
        //从先序中确定根
        char rootdata=preorder[0];
        TreeNode *PNewTreeNode = new TreeNode;//在堆上面申请一个新的二叉树节点
        PNewTreeNode->data=rootdata;
        //拿根去切割中序
        int weizhi =inorder.find(rootdata);//weizhi是根在中序序列中出现的下标
//        preorder.substr(1,weizhi);//将preorder切割，取出从下标1开始，长度为weizhi的子串
        PNewTreeNode->leftChild = rebuild(preorder.substr(1,weizhi),inorder.substr(0,weizhi));
        PNewTreeNode->rightChild= rebuild(preorder.substr(weizhi+1),inorder.substr(weizhi+1));
        return PNewTreeNode;
    }
}
void postOrder(TreeNode *root){
    if (root == NULL){
        return;
    } else{
        postOrder(root->leftChild);
        postOrder(root->rightChild);
        printf("%c",root->data);
    }
}
int main(){
    char PreOrder[30];
    char InOrder[30];
    while (scanf("%s%s",PreOrder,InOrder)!=EOF){
        TreeNode * root = rebuild(PreOrder,InOrder);
        postOrder(root);
        printf("\n");
    }
}