给定先中后层序遍历中任意两个, 还原树结构

发表于 | 更新于 | 分类于 ，

1. 说明

任意给定先序、中序、后序、层序遍历中的任意两个，能否重新还原一棵树。

这个题的答案是必须要有中序序列，然后其他三种任意挑选一个。

2. 方法

方法其实都一样：

  • 遍历三种序列，依次找到顶点结点
  • 找到该顶点在中序遍历中的位置，分割左右子树结点的集合

3. 先序+中序

由于先序是“根-左-右”，所以我们从前往后遍历，肯定能先遇到根节点。

假如有：

先序：ABDECFG
中序: DEBACGF

下面依次遍历先序结点

  1. 结点 A

A为根节点，找到中序序列中 A 的位置，分割左右子树集合

DEB A CGF

graph TD
A --> L(DEB)
A --> R(CGF)
  1. 结点 B

DE B A

B 为根节点，直接和 A 相连；且 B 在 A 的左子树；B 的左子树结点集合为 {D, E}；B 没有右子树

所以

graph TD
A --> B
B --> L(DE)
B --> 1[null]
A --> R(CGF)
  1. 结点 D、E

D E B

先是 D，直接和 B 相连，E 在 D 的右子树上

graph TD
A --> B
B --> D
D --> 1[null]
D --> E
B --> x[null]
A --> R(CGF)
  1. 结点 C

C GF

C 直接和 A 相连，它没有左子树，右子树的结点集合为 {G, F}。

graph TD
A --> B
B --> D
D --> 1[null]
D --> E
B --> x[null]
A --> C
C --> y[null]
C --> z[GF]
  1. 结点 F、G

同理

graph TD
A --> B
B --> D
D --> 1[null]
D --> E
B --> x[null]
A --> C
C --> y[null]
C --> F
F --> G
F --> z[null]

其他的也差不多，后序遍历就是从后往前，层序遍历同样从前往后。

4. 例题

给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。

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
#include <bits/stdc++.h>
using namespace std;

string inorder, preorder;

void BuildPost(int prefirst, int prelast, int infirst, int inlast)
{
    char root = preorder[prefirst];
    int at;
    for (at = infirst; at <= inlast; ++at)
        if (inorder[at] == root)
            break;
    int leftNodes = at - infirst, rightNodes = inlast - at;
    if (at != infirst)
    {
        BuildPost(prefirst + 1, prefirst + leftNodes, infirst, at - 1);
    }
    if (at != inlast)
    {
        BuildPost(prelast - rightNodes + 1, prelast, at + 1, inlast);
    }
    cout << root;
}

int main()
{
    while (cin >> preorder >> inorder)
    {
        BuildPost(0, preorder.length() - 1, 0, inorder.length() - 1);
        cout << endl;
    }
    return 0;
}

给定中序和后序，求先序

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
42
43
44
45
46
#include <string>
#include <iostream>
using namespace std;

string postorder;
string inorder;

/**
[postBeg, postEnd] 和 [inBeg, inEnd] 分别代表了同一棵树的后序遍历和中序遍历序列
*/
void ToPre(int postBeg, int postEnd, int inBeg, int inEnd)
{
    //根在最后一个结点
    char ch = postorder[postEnd];
    int at;
    //找到根节点在中序序列中的位置
    for (int i = inBeg; i <= inEnd; ++i)
    {
        if (inorder[i] == ch)
        {
            at = i;
            break;
        }
    }
    cout << ch;
    //计算左子树和右子树结点的个数
    int leftNodes = at - inBeg, rightNodes = inEnd - at;
    //遍历左子树 和 右子树
    if (leftNodes != 0)
    {
        ToPre(postBeg, postBeg + leftNodes - 1, inBeg, at - 1);
    }
    if (rightNodes != 0)
    {
        ToPre(postEnd - rightNodes, postEnd - 1, at + 1, inEnd);
    }
}

int main()
{
    cin >> inorder;
    cin >> postorder;
    ToPre(0, postorder.length() - 1, 0, inorder.length() - 1);
    cout << endl;
    return 0;
}