给定树的遍历序-重建一棵可能的树

摘要: BFS 序和 DFS 序结合的经典问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在文章 遍历序的概念与性质 中，我们了解了树的各种遍历序。本文我们看一个直接的问题，如何从树的遍历序，构造出相应的树。

在解决这个问题的过程中，我们会用到 BFS 序和 DFS 序的性质。

问题

问题：给定一颗树的 bfs 序和 dfs 序，结点编号小的优先历遍，建立一棵可能的树；

输入

8
4 3 5 1 2 8 7 6
4 3 1 7 2 6 5 8

输出

1: 7
2: 6
3: 1 2
4: 3 5
5: 8
6:
7:
8:

---

dfs 序的性质

• dfs序中一个结点的子树结点一定是连续的。

bfs，dfs序中前后相邻节点的性质

在BFS序中，与点 node 相邻的下一个点可能有三种可能性：

• (1) node 的第一后兄弟(node 所在层还没结束)
• (2) node 的子节点(node 所在层结束)
• (3) node 的兄弟节点的子节点(node 所在层结束)

在DFS序中，与点 node 相邻的下一个点可能有三种可能性：

• (1) node 的子节点(node 子树尚没结束)
• (2) node 的第一后兄弟(node 子树已经结束，但父节点子树还没结束)
• (3) 与 node 的父节点子树均无关了（父节点子树结束）

设两个节点为 u，v ，且它们的 BFS 序分别为 bfs(u), bfs(v)。用这两条性质可以推出关于 bfs(u), bfs(v) 关系的重要结论:

<1> u, v 在 DFS 序中相邻，且 v 是 u 的下一点

如果 bfs(v) = bfs(u) + 1 && v > u 那么，v 一定可以视为 u 的第一后兄弟。

因为 u, v 在两个序列里都相邻，此时前面提到的 u 与 v 的三种情况，只剩两种了：

1. 如果 v 是 u 的第一后兄弟(此时就不用”视为”了，本来就是)
2. 如果 v 是 u 的子节点，下面看看 v 为什么可以视为 v 的第一后兄弟

此时由于二者在 BFS 序中相邻，因此和 u 在同一层的节点都遍历到了
在这种情况下，如果 u 的同一层还有别的节点，即 u 有前兄弟，那么 v 一定是 u 的前兄弟的子节点
而此时 v 时 u 的孩子，因此 u 所在的那一层只有 u 一个节点
此时把 v 及其子树提上来，可以让 v 变成 u 的后兄弟而不改变 BFS 序和 DFS 序。

<2> bfs(v) > bfs(u) + 1

在 bfs(v) = bfs(u) + 1 的这个结论的基础上，可以进一步推出 bfs(v) > bfs(u) + 1 的结论： v 不可能是 u 的后兄弟，只能是 u 的子节点。

因为看 DFS 序相邻相邻节点的三种情况，v 不能是节点 u 的第一后兄弟，因为他们的 BFS 序不相邻；v 也不可能与 u 的父节点子树无关，因为 v 的 BFS 序在 u 后面

<3> bfs(v) < bfs(u)

如果 bfs(v) < bfs(u) 那就只能是 v 与 u 的父节点子树无关的情况了，此时在 DFS 序中 v 回到了u 的父辈及以上。即 u 及其子树被处理完了，忽略 u 就好，具体实现时弹栈就好。

完整算法

计算每个节点的 BFS 序 bfs_order[x] := 节点 x 的 BFS 序
枚举 DFS 序列元素，将根节点进栈
此后的枚举过程，记当前节点为 v，栈顶节点为 u
    while(true)
        (1) bfs_order[v] > bfs_order[u] + 1 : v 是 u 的子节点                <1> 的情况
        (2) bfs_order[v] == bfs_order[u] + 1 && u > v : v 是 u 的子节点      <2> 的情况
        (3) 其它情况，例如 bfs_order[v] < bfs_order[u] 将 u 弹出             <3> 的情况以及未覆盖到的情况
        (4) 特例：栈顶为根节点: v 是 u 的子节点
        出现(1)(2)(4)，记录 v 是 u 的子节点，将 v 进栈，break
        出现(3) 不断弹出，直至出现(1)(2)(4)

代码 (C++)

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <stack>

using namespace std;

vector<vector<int>> build(const vector<int>& bfs_order, const vector<int>& dfs_seq)
{
    stack<int> st;
    int n = dfs_seq.size();
    st.push(dfs_seq[0]);
    vector<vector<int>> g(n + 1);
    for(int i = 1; i < n; ++i)
    {
        int v = dfs_seq[i];
        while(true)
        {
            int u = st.top();
            if((bfs_order[v] > bfs_order[u] + 1) 
               || (bfs_order[v] == bfs_order[u] + 1 && u > v) 
               || (u == dfs_seq[0]))
            {
                g[u].push_back(v);
                st.push(v);
                break;
            }
            else
                st.pop();
        }
    }
    return g;
}

int main()
{
    ifstream f("build.test");
    string str;
    cout << "输入" << endl;
    getline(f, str);
    int n;
    stringstream ss;
    ss << str;
    ss >> n;
    cout << n << endl;
    getline(f, str);
    ss.clear();
    ss << str;
    vector<int> bfs_order(n + 1, -1);
    for(int i = 1; i <= n; ++i)
    {
        int x;
        ss >> x;
        bfs_order[x] = i;
    }
    cout << "bfs order: ";
    for(int i: bfs_order)
        cout << i << " ";
    cout << endl;
    getline(f, str);
    ss.clear();
    ss << str;
    vector<int> dfs_seq(n, -1);
    cout << "dfs order: ";
    for(int i = 0; i < n; ++i)
        ss >> dfs_seq[i];
    for(int i: dfs_seq)
        cout << i << " ";
    cout << endl;
    vector<vector<int>> g = build(bfs_order, dfs_seq);
    cout << "----------done----------" << endl;
    for(int i = 1; i <= n; ++i)
    {
        cout << i << ": ";
        for(int j = 0; j < (int)g[i].size(); ++j)
            cout << g[i][j] << " ";
        cout << endl;
    }
}

测试

输入给定树的 bfs 序和 dfs 序，输出重建的树的边表。

---