题解 | #二叉树遍历#

递归建树，子树为空返回NULL

#include <iostream>
using namespace std;
struct treeNode {
    char letter;
    treeNode* leftChild;
    treeNode* rightChild;
    treeNode(char c) {
        letter = c;
        leftChild = NULL;
        rightChild = NULL;
    }
};
treeNode* buildTree(string preOrderStr, string inOrderStr) {
    if (preOrderStr.size() == 0) {
        return NULL;
    }
    treeNode* newNode = new treeNode(preOrderStr[0]);

    int pos = inOrderStr.find(preOrderStr[0]);
    newNode->leftChild = buildTree(preOrderStr.substr(1, pos), inOrderStr.substr(0,
                                   pos));
    newNode->rightChild = buildTree(preOrderStr.substr(pos + 1),
                                    inOrderStr.substr(pos + 1));
    return newNode;
}
void postOrder(treeNode* root) {
    if (root == NULL) return;
    postOrder(root->leftChild);
    postOrder(root->rightChild);
    cout << root->letter;
}
int main() {
    string a, b;
    while (cin >> a >> b) { // 注意 while 处理多个 case
        treeNode* tree = buildTree(a, b);
        postOrder(tree);
        cout <<  endl;
    }
}
// 64 位输出请用 printf("%lld")