题解 | #二叉树遍历#

#include "cstdio"
#include "string"
using namespace std;

struct BinTNode {
    char data;
    struct BinTNode* lc;
    struct BinTNode* rc;
};
/*
描述
二叉树的前序、中序、后序遍历的定义： 前序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树；
 中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；
 后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。
 给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。
输入描述：
两个字符串，其长度n均小于等于26。 第一行为前序遍历，第二行为中序遍历。 二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。
输出描述：
输入样例可能有多组，对于每组测试样例， 输出一行，为后序遍历的字符串。
 */
BinTNode* rebuild(string preOrder, string inOrder) {
    if (preOrder.empty()) {
        return NULL;
    }

    BinTNode* root = (BinTNode*) malloc(sizeof(BinTNode));
    char root_data = preOrder[0];
    root->data = root_data;

    int index = inOrder.find(root_data);
    string inorder_left = inOrder.substr(0, index);
    string inorder_right = inOrder.substr(index + 1);
    string pre_left = preOrder.substr(1, index);
    string pre_right = preOrder.substr(index + 1);
    //todo 前序的来自于前序 中序的来自中序 长度相等
    root->lc = rebuild(pre_left, inorder_left);
    root->rc = rebuild(pre_right, inorder_right);
    return root;
}

void postoder(BinTNode* root) {
    if (NULL == root)
        return;
    postoder(root->lc);
    postoder(root->rc);
    printf("%c", root->data);
}

int main() {
    char preOrder[32];
    char inOrder[32];
    while (EOF != scanf("%s%s", preOrder, inOrder)) {
        BinTNode* root = rebuild(preOrder, inOrder);
        postoder(root);
        printf("\n");
    }
    return 0;
}

分析 此题使用了

1. 前序遍历的第一个元素来确定根元素；
2. 中序遍历中的根元素所在位置index，就是根的左子树的长度；
3. 前序遍历跳过第一个元素，往后index个元素就是前序遍历的左子树；
4. 同一个根节点的左子树长度应该相等；
5. 继续使用前序的左子树串 和 中序的左子树串进行 drill down, 也就是分治，也即是元素数量从1到0之后，往上悬挂null
6. 树的定义本身就是递归定义的；
7. 树的遍历和树的递归定义有直接关系，因此可以使用递归；
8. 又，树的前序 和 后续遍历 得到的结果，可以将大规模问题 分解为相同问题的更小规模，从而继续递归分解下去；
9. 每一层的malloc 就是治，治理完毕之后， 再 return 就是归