Hz 吐泡泡

题意

给出 n 个互不相同的数，按顺序把它们插入一棵二叉查找树。

题目要求输出：

这棵树的最大深度，格式为 deep=...
这棵树的后序遍历

思路

最直接的办法是按题意真的模拟 BST 插入，然后 DFS 求答案。

先看一个可以直接验证想法的朴素解：

cpp

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node *left;
    Node *right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

// 按题意逐个插入 BST，适合小数据验证与教学理解。
void insert_node(Node *root, int x, int depth, int &max_depth) {
    max_depth = max(max_depth, depth);
    if (x < root->val) {
        if (root->left == nullptr) {
            root->left = new Node(x);
            max_depth = max(max_depth, depth + 1);
            return;
        }
        insert_node(root->left, x, depth + 1, max_depth);
    } else {
        if (root->right == nullptr) {
            root->right = new Node(x);
            max_depth = max(max_depth, depth + 1);
            return;
        }
        insert_node(root->right, x, depth + 1, max_depth);
    }
}

void postorder(Node *node, vector<int> &ans) {
    if (node == nullptr) {
        return;
    }
    postorder(node->left, ans);
    postorder(node->right, ans);
    ans.push_back(node->val);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    Node *root = new Node(a[1]);
    int max_depth = 1;
    for (int i = 2; i <= n; ++i) {
        insert_node(root, a[i], 1, max_depth);
    }

    vector<int> ans;
    postorder(root, ans);

    cout << "deep=" << max_depth << '\n';
    for (int x : ans) {
        cout << x << '\n';
    }
    return 0;
}

brute.cpp 显式建树后再递归输出后序遍历，适合帮助理解和对拍。但它最坏会退化成 $O(n^2)$ ，面对 3e5 的数据不够稳。

关键观察是：一个新值插入 BST 时，它的父亲只可能是当前已插入值中的前驱或后继。

样例树

这张图展示样例插入完成后的 BST 结构：

graph TD
  A["1"] -->|right| B["4"]
  B -->|left| C["3"]
  B -->|right| D["9"]
  C -->|left| E["2"]
  D -->|left| F["7"]
  D -->|right| G["10"]
  G -->|right| H["35"]

从图里可以看到，样例的最大深度是 5。后序遍历按“左、右、根”输出，所以答案正好是 2 3 7 35 10 9 4 1。真正需要解决的问题，只剩下如何在线恢复这棵 BST 的父子关系。

维护一个有序集合保存已经插入的值：

用 lower_bound 找到当前值的后继
同时取前驱
这两个候选里，插入更晚的那个就是当前点的父亲

这样每次插入只需要一次有序集合查询，就能在 $O(log n)$ 时间内确定父子关系。

树建好后，再用双栈做一次迭代后序遍历：

第一栈负责遍历整棵树
第二栈把访问顺序翻转成“左、右、根”

同时在连边时维护每个节点的深度，就能顺手得到最大深度。

代码

cpp

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300000 + 5;

static int n;
static int value_arr[MAXN];
static int left_son[MAXN];
static int right_son[MAXN];
static int depth_arr[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> value_arr[i];
    }

    int max_depth = 1;
    depth_arr[1] = 1;
    set<pair<int, int>> ordered_values;
    ordered_values.insert({value_arr[1], 1});

    for (int i = 2; i <= n; ++i) {
        int parent;
        auto it = ordered_values.lower_bound({value_arr[i], 0});

        if (it == ordered_values.begin()) {
            // 没有前驱，只能接到后继的左边。
            parent = it->second;
            left_son[parent] = i;
        } else if (it == ordered_values.end()) {
            // 没有后继，只能接到前驱的右边。
            auto pre_it = prev(it);
            parent = pre_it->second;
            right_son[parent] = i;
        } else {
            auto pre_it = prev(it);
            int pre_idx = pre_it->second;
            int nxt_idx = it->second;

            // 前驱和后继里，插入更晚的那个就是当前点的父亲。
            if (pre_idx > nxt_idx) {
                parent = pre_idx;
                right_son[parent] = i;
            } else {
                parent = nxt_idx;
                left_son[parent] = i;
            }
        }

        depth_arr[i] = depth_arr[parent] + 1;
        max_depth = max(max_depth, depth_arr[i]);
        ordered_values.insert({value_arr[i], i});
    }

    stack<int> s1;
    stack<int> s2;
    s1.push(1);

    // 用双栈迭代输出后序遍历，避免极端链状树导致递归爆栈。
    while (!s1.empty()) {
        int u = s1.top();
        s1.pop();
        s2.push(u);

        if (left_son[u] != 0) {
            s1.push(left_son[u]);
        }
        if (right_son[u] != 0) {
            s1.push(right_son[u]);
        }
    }

    cout << "deep=" << max_depth << '\n';
    while (!s2.empty()) {
        cout << value_arr[s2.top()] << '\n';
        s2.pop();
    }
    return 0;
}

复杂度

每次插入需要 $O(log n)$ 找前驱和后继，后序遍历是 $O(n)$ ，所以总时间复杂度是 $O(n log n)$ ，空间复杂度是 $O(n)$ 。

总结

这题难点不在 BST 本身，而在看出“新点的父亲只可能是前驱或后继”。抓住这一点后，用有序集合在线找父亲，就能把最坏 $O(n^2)$ 的插入过程优化到 $O(n log n)$ 。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

样例树

代码

复杂度

总结

一图流解析