已知二叉树的前序遍历、中序遍历，输出其后序遍历。

例如：

  • 前序：DBEACF
  • 中序：ABDEFC
1
2
3
    A
 B     C
D E   F

思路：

  1. 前序的第一个字符，是树根root，也是中序的中间字符，分割左右子树的中序；
  2. 中序左右子树长度，得到前序左右子树；
  3. 递归左/右的前序+中序

原来： 前序 DBE|==A==|CF、中序 ==A==|BDE|FC

A 左： 前序 ==D==|B|E、中序 B|==D==|E

A 右： 前序 ==C==|F、中序 F|==C==

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cstring>
using namespace std;

struct Node
{
    Node *left = NULL, *right = NULL;
    char data = '?';

    void LRD_Print() // 后序遍历递归
    {
        if (left)
            left->LRD_Print();
        if (right)
            right->LRD_Print();
        cout << data;
    }
};

Node *parse(string pre, string mid)
{
    if (!pre.length()) return NULL; // 叶子结点
    
    Node *node = new Node();
    node->data = pre.substr(0, 1).c_str()[0]; // 前序遍历第一个字符串就是root
    int root_pos = mid.find(node->data);      // 中序的root位置，也是左子树长度

    node->left = parse(pre.substr(1, root_pos), mid.substr(0, root_pos));
    node->right = parse(pre.substr(root_pos + 1), mid.substr(root_pos + 1));

    return node;
}

int main()
{
    string pre = "ABDECF"; // 前序遍历
    string mid = "DBEAFC"; // 中序遍历
    Node *node = parse(pre, mid);
    if (node != NULL)
        node->LRD_Print();
}

运行结果：

1
DEBFCA