【牛客网】KY11 二叉树遍历

题目只给了先序遍历，然后让我们输出对应的中序遍历，同样的，首先根据先序遍历构建二叉树，因为空树是用#号表示出来，所以输入其实就相当于是一棵完全二叉树，则可以唯一确定一颗二叉树，然后我们只需要根据当前的字符是否为#号，来判断是否需要返回nullptr即可：

#include
#include

using namespace std;

int n;
string preOrder;

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

TreeNode* Build(){
    char ch = preOrder[n++];  //需要首先取出该字符
    if(ch == '#') return nullptr;
    TreeNode *root = new TreeNode(ch);
    root->lchild = Build();
    root->rchild = Build();
    return root;
}

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

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