P1030 [NOIP 2001 普及组] 求先序排列 - 洛谷

这道题目是一个很重要的树题，必须掌握，即使很简单也要写一篇。

解题思路

核心逻辑依然是利用二叉树遍历的特性：

  1. 后序遍历的最后一个字符是当前子树的根节点；
  2. 中序遍历中，根节点左侧是左子树，右侧是右子树；
  3. 用下标边界替代字符串切割，通过递归依次输出根、左子树、右子树（先序规则）。

具体通过 4 个下标定位子区间（均为闭区间）：

  • in_l/in_r：当前子树在中序字符串中的左右边界；
  • post_l/post_r：当前子树在后序字符串中的左右边界；
  • 左子树节点数 = 根在中序的位置 - 中序左边界；
  • 基于左子树节点数，可推导出左右子树在后序中的边界范围。

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;

string inorder, postorder; // 两个字符串表示输入的中序遍历和后序遍历

void preorder(int in_l, int in_r, int post_l, int post_r) { // 中后序遍历求前序遍历函数
    if(in_l > in_r) // 如果当前子树无结点，直接返回
        return;

    cout << postorder[post_r]; // 后序遍历的最后一位是根，直接输出

    int k = inorder.find(postorder[post_r]); // 中序遍历中的根位置，以此划分左右树
    int left_size = k - in_l; // 表示左子树的大小

    preorder(in_l, k - 1, post_l, post_l + left_size - 1); // 左子树部分
    preorder(k + 1, in_r, post_l + left_size, post_r - 1); // 右子树部分
}

int main() {
    cin >> inorder >> postorder;
    preorder(0, inorder.length() - 1, 0, postorder.length() - 1);
    return 0;
}

代码核心解释

  1. **递归函数 preOrder**：

    • 终止条件：in_l > in_r，表示当前子树无节点，直接返回；
    • 根节点：取后序区间最后一个字符postOrder[post_r]，直接输出（先序先输出根）；
    • 根位置：k是根在中序字符串中的索引，以此划分左右子树；
    • 左子树递归：中序区间[in_l, k-1]，后序区间[post_l, post_l + left_size - 1]；
    • 右子树递归：中序区间[k+1, in_r]，后序区间[post_l + left_size, post_r - 1]。

  2. 主函数：

    • 读取中序和后序字符串，获取节点总数n；
    • 初始调用递归函数，传入整棵树的边界（中序 / 后序均为[0, n-1]）。