题解：UVA12347 Binary Search Tree

CleverSea · 2025-02-09 16:29:52 · 题解

UVA12347 Binary Search Tree 题解

题意简述

给定二叉搜索树的前序遍历结果，输出该树的后序遍历结果。

前置知识

众所周知，二叉搜索树具有下列性质：

• 左子树的所有节点的键值小于根节点的键值；
• 右子树的所有节点的键值大于根节点的键值；
• 左右子树也必须是二叉搜索树。

又众所周知，前序遍历的顺序是：根节点 -> 左子树 -> 右子树；后序遍历的顺序是：左子树 -> 右子树 -> 根节点。

• 举个栗子：

在这棵二叉搜索树中，前序遍历为 18 -> 10 -> 7 -> 9 -> 15 -> 20 -> 22 ；后序遍历为 9 -> 7 -> 15 -> 10 -> 22 -> 20 -> 18 。

思路

由于前序遍历的第一个元素是根节点，我们可以利用二叉搜索树的性质，将数组分为左子树和右子树。左子树的所有元素小于根节点，右子树的所有元素大于根节点。递归处理左右子树，最后输出根节点即可。时间复杂度为 O(n) ，其中 n 是节点的数量。

代码实现

#include <iostream>
#include <vector>
using namespace std;

// 递归函数，构建二叉搜索树并生成后序遍历结果
void build(vector<int>& pre, int start, int end, vector<int>& post) {
    if (start > end) return; // 终止条件
    int root = pre[start]; // 前序遍历的第一个元素是根节点
    int i = start + 1;
    // 找到左子树和右子树的分界点
    while (i <= end && pre[i] < root) {
        i++;
    }
    // 递归处理左子树
    build(pre, start + 1, i - 1, post);
    // 递归处理右子树
    build(pre, i, end, post);
    // 将根节点加入后序遍历结果
    post.push_back(root);
}

int main() {
    vector<int> pre;
    int val;
    while (cin >> val) {
        pre.push_back(val);
    }
    vector<int> post;
    build(pre, 0, pre.size() - 1, post);
    // 输出后序遍历结果
    for (int i = 0; i < post.size(); i++) {
        cout << post[i] << endl;
    }
    return 0; // 优雅地结束
}