二叉树算法实战：计算深度与求先序排列

题目描述

问题二：求先序排列 参考链接：洛谷 P1030

解题思路

这道题考察的是根据中序遍历和后序遍历还原二叉树并输出先序遍历。关键点在于利用后序遍历的最后一个元素确定当前子树的根节点，然后在中序遍历中找到该根节点的位置，从而划分出左子树和右子树的区间。

具体步骤如下：

1. 确定根节点：后序序列的末尾字符即为当前子树的根。
2. 划分区间：在中序序列中找到根节点，其左侧为左子树范围，右侧为右子树范围。
3. 递归处理：根据划分出的区间长度，在后序序列中对应切分出左右子树的后序序列，继续递归。

注意：这里需要仔细维护四个边界参数（中序的左右、后序的左右），确保区间不越界且逻辑正确。

代码实现

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

string inorder, postorder;

/**
 * @param l1 r1 中序遍历的左右边界
 * @param l2 r2 后序遍历的左右边界
 */
void dfs(int l1, int r1, int l2, int r2) {
    if (l1 > r1) return; // 递归出口：区间无效

    // 后序遍历的最后一个元素是当前子树的根
    cout << postorder[r2];

    // 在中序遍历中寻找根节点的位置 p
    int p = l1;
    while (inorder[p] != postorder[r2]) p++;

    // 计算左子树的大小
    int leftLen = p - l1;

    // 递归处理左子树
    // 中序：[l1, p-1]
    // 后序：[l2, l2 + leftLen - 1]
    dfs(l1, p - 1, l2, l2 + leftLen - 1);

    // 递归处理右子树
    // 中序：[p+1, r1]
    // 后序：[l2 + leftLen, r2 - 1]
    dfs(p + 1, r1, l2 + leftLen, r2 - 1);
}

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