专栏文章

题解: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 题解

题意简述

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

前置知识

众所周知,二叉搜索树具有下列性质:
  • 左子树的所有节点的键值小于根节点的键值;
  • 右子树的所有节点的键值大于根节点的键值;
  • 左右子树也必须是二叉搜索树。
又众所周知,前序遍历的顺序是:根节点 -> 左子树 -> 右子树;后序遍历的顺序是:左子树 -> 右子树 -> 根节点。
  • 举个栗子:
在这棵二叉搜索树中,前序遍历为 1818 -> 1010 -> 77 -> 99 -> 1515 -> 2020 -> 2222 ;后序遍历为 99 -> 77 -> 1515 -> 1010 -> 2222 -> 2020 -> 1818

思路

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

代码实现

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 条评论,欢迎与作者交流。

正在加载评论...