题解 | #二叉树遍历#

//若字符后面不是#，则一定为左子树，左子树递归完后（##结束），递归右子树即可
#include "stdio.h"
#include "string"
using namespace std;
struct TreeNode{
    char data;
    TreeNode *leftChild;
    TreeNode *rightChild;
};

TreeNode *RebuildTree(string &preList){
    if (preList.size()==0)
        return NULL;
    else{
        if(preList[0] == '#'){
            preList = preList.substr(1);
            return NULL;
        } else{
            TreeNode *node = new TreeNode;
            node->data = preList[0];
            preList = preList.substr(1);
            node->leftChild = RebuildTree(preList);
            node->rightChild = RebuildTree(preList);
            return node;
        }
    }
}

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

int main(){
    char preList[101];
    while (scanf("%s",preList)!=EOF){
        string str = preList;
        TreeNode *root = RebuildTree(str);
        InOrder(root);
        printf("\n");
    }
}