【牛客网】KY212 二叉树遍历

因为题目提供了前序遍历和中序遍历，因此我们可以唯一确定一棵二叉树，那么我们可以先根据前序遍历和中序遍历构造出这棵树，然后再使用后序遍历的方法进行遍历输出即可：

#include
#include

using namespace std;

struct TreeNode{
    char data;
    struct TreeNode *lchild, *rchild;
    TreeNode(char c): data(c), lchild(nullptr), rchild(nullptr){}
};

TreeNode* Build(string preOrder, string inOrder){
    if(preOrder.size() == 0) return nullptr;
    char ch = preOrder[0];
    TreeNode *root = new TreeNode(ch);
    int position = inOrder.find(ch);
    root->lchild = Build(preOrder.substr(1, position), inOrder.substr(0, position));
    root->rchild = Build(preOrder.substr(position + 1), inOrder.substr(position + 1));
    return root;
}

void postOrder(TreeNode *root){
    if(root != nullptr){
        postOrder(root->lchild);
        postOrder(root->rchild);
        printf("%c", root->data);
    }
}

int main(){
    string preOrder, inOrder;
    while(cin>>preOrder>>inOrder){
        TreeNode *root = Build(preOrder, inOrder);
        postOrder(root);
        printf("n");
    }
    return 0;
}