题解 | #二叉树遍历#

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

struct TreeNode {
    char data;
    TreeNode* leftChild;
    TreeNode* rightChild;
};

/**
 * KY212
 * 根据先序遍历和中序遍历重构二叉树
 * @param preOrder 先序遍历
 * @param inOrder 中序遍历
 * @return 该数的根结点
 */
TreeNode* rebuild(string preOrder, string inOrder) {
    if (preOrder.size() == 0) { //不能再分割了
        return NULL;
    }
    //新建在堆上
    TreeNode* treeNode = new TreeNode;
    char data = preOrder[0]; //第一个为树结点的值
    treeNode->data = data;
    int pos = inOrder.find(data); //找到data在inOrder中的位置
    /**
     * string.substr(startIndex, length) 截取子串:从startIndex开始往后length个长度
     * string.substr(startIndex) 截取子串:从startIndex开始一直到结尾
     */
    treeNode->leftChild = rebuild(preOrder.substr(1, pos), inOrder.substr(0, pos));
    treeNode->rightChild = rebuild(preOrder.substr(pos + 1),
                                   inOrder.substr(pos + 1));
    return treeNode;

}

/**
 * 后序遍历
 * @param root
 */
void PostOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    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* treeNode;
        treeNode = rebuild(preOrder, inOrder);
        PostOrder(treeNode);
        printf("\n");
    }
}