专栏文章
题解:UVA12347 Binary Search Tree
UVA12347题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @miqara25
- 此快照首次捕获于
- 2025/12/04 01:44 3 个月前
- 此快照最后确认于
- 2025/12/04 01:44 3 个月前
UVA12347 Binary Search Tree 题解
题意简述
给定二叉搜索树的前序遍历结果,输出该树的后序遍历结果。
前置知识
众所周知,二叉搜索树具有下列性质:
- 左子树的所有节点的键值小于根节点的键值;
- 右子树的所有节点的键值大于根节点的键值;
- 左右子树也必须是二叉搜索树。
又众所周知,前序遍历的顺序是:根节点 -> 左子树 -> 右子树;后序遍历的顺序是:左子树 -> 右子树 -> 根节点。
- 举个栗子:

在这棵二叉搜索树中,前序遍历为 -> -> -> -> -> -> ;后序遍历为 -> -> -> -> -> -> 。
思路
由于前序遍历的第一个元素是根节点,我们可以利用二叉搜索树的性质,将数组分为左子树和右子树。左子树的所有元素小于根节点,右子树的所有元素大于根节点。递归处理左右子树,最后输出根节点即可。时间复杂度为 ,其中 是节点的数量。
代码实现
CPP#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; // 优雅地结束
}
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...