P1030 求先序排列

calendar May 11, 2026 · 4 分钟阅读 · 二叉树 递归  ·
分享到: linkedin copy

文章目录

题目信息

字段 内容
题号 P1030
难度 普及-
知识点 二叉树、递归、遍历

题目描述

给定一棵二叉树的中序遍历和后序遍历序列，请你输出这棵二叉树的先序遍历序列。

三种遍历方式定义：

  • 先序遍历（Preorder）：根 → 左 → 右
  • 中序遍历（Inorder）：左 → 根 → 右
  • 后序遍历（Postorder）：左 → 右 → 根

输入格式

  • 第一行：中序遍历序列（一个字符串）
  • 第二行：后序遍历序列（一个字符串）

输出格式

  • 输出先序遍历序列

样例

输入 #1：

ABDEC
AEDBCB

输出 #1：

BDABEC

解题思路

核心思想

根据后序遍历找根，根据中序遍历分左右子树。

  1. 后序遍历的最后一个节点一定是根（因为后序顺序是左→右→根）
  2. 在中序遍历中找到根，根左边是左子树，右边是右子树
  3. 递归处理左右子树，先输出根（先序顺序）

算法流程

build(中序, 后序):
    if 中序为空: return

    根 = 后序最后一个字符
    在中序中找到根的位置 k

    左中序 = 中序[0..k-1]
    右中序 = 中序[k+1..end]
    左后序 = 后序[0..左中序长度-1]
    右后序 = 后序[左中序长度..end-1]

    输出根  // 先序：根在前
    build(左中序, 左后序)
    build(右中序, 右后序)

示例解析

中序: ABDEC
后序: AEDBCB

1. 后序最后一个 B 是根
2. 中序中找到 B：A D | B | E C
   - 左子树: AD
   - 右子树: EC

3. 左子树递归:
   中序: AD, 后序: AD
   - 根 = D（后序最后）
   - 中序中 D: A | D | E（空）
   - 输出 D
   - 递归 A

4. 右子树递归:
   中序: EC, 后序: EC
   - 根 = C
   - 中序中 C: E | C
   - 输出 C
   - 递归 E

先序结果: B D A E C

完整代码

C++

#include <bits/stdc++.h>

/**
 * 根据中序和后序遍历构建先序遍历
 * @param in_order 中序遍历序列
 * @param post_order 后序遍历序列
 */
void BuildPreorder(const std::string& in_order,
                   const std::string& post_order) {
    if (in_order.empty()) {
        return;
    }

    // 后序遍历的最后一个节点是根节点
    char root = post_order.back();

    // 在中序遍历中找到根节点的位置
    size_t k = in_order.find(root);

    // 先输出根节点（先序：根 → 左 → 右）
    std::cout << root;

    // 递归处理左子树
    BuildPreorder(
        in_order.substr(0, k),
        post_order.substr(0, k)
    );

    // 递归处理右子树
    BuildPreorder(
        in_order.substr(k + 1),
        post_order.substr(k, in_order.size() - k - 1)
    );
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::string in_order;
    std::string post_order;
    std::cin >> in_order >> post_order;

    BuildPreorder(in_order, post_order);
    std::cout << "\n";

    return 0;
}

Go

package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

// build 根据中序和后序遍历构建先序遍历
func build(inOrder, postOrder string) {
	if len(inOrder) == 0 {
		return
	}

	// 后序遍历的最后一个节点是根节点
	root := postOrder[len(postOrder)-1]

	// 在中序遍历中找到根节点的位置
	k := strings.Index(inOrder, string(root))

	// 先输出根节点
	fmt.Print(string(root))

	// 递归处理左子树
	build(inOrder[:k], postOrder[:k])

	// 递归处理右子树
	build(inOrder[k+1:], postOrder[k:len(postOrder)-1])
}

func main() {
	in := bufio.NewReader(os.Stdin)
	var inOrder, postOrder string
	fmt.Fscan(in, &inOrder, &postOrder)

	build(inOrder, postOrder)
	fmt.Println()
}

Java

import java.io.*;
import java.util.*;

public class Main {
    private static String inOrder;
    private static String postOrder;

    /**
     * 根据中序和后序遍历构建先序遍历
     */
    private static void build(int inL, int inR, int postL, int postR) {
        if (inL > inR) {
            return;
        }

        // 后序遍历的最后一个节点是根节点
        char root = postOrder.charAt(postR);

        // 在中序遍历中找到根节点的位置
        int k = inOrder.indexOf(root, inL);

        // 先输出根节点
        System.out.print(root);

        // 递归处理左子树
        build(inL, k - 1, postL, postL + k - inL - 1);

        // 递归处理右子树
        build(k + 1, inR, postL + k - inL, postR - 1);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        inOrder = br.readLine();
        postOrder = br.readLine();

        build(0, inOrder.length() - 1, 0, postOrder.length() - 1);
        System.out.println();
    }
}

Python

import sys


def build(in_order: str, post_order: str) -> None:
    """
    根据中序和后序遍历构建先序遍历

    Args:
        in_order: 中序遍历序列
        post_order: 后序遍历序列
    """
    if not in_order:
        return

    # 后序遍历的最后一个节点是根节点
    root = post_order[-1]

    # 在中序遍历中找到根节点的位置
    k = in_order.index(root)

    # 先输出根节点（先序：根 → 左 → 右）
    print(root, end='')

    # 递归处理左子树
    build(in_order[:k], post_order[:k])

    # 递归处理右子树
    build(in_order[k + 1:], post_order[k:-1])


def main() -> None:
    in_order = sys.stdin.readline().strip()
    post_order = sys.stdin.readline().strip()

    build(in_order, post_order)
    print()


if __name__ == "__main__":
    main()

JavaScript

'use strict';

let inOrder;
let postOrder;

/**
 * 根据中序和后序遍历构建先序遍历
 * @param {number} inL - 中序左边界
 * @param {number} inR - 中序右边界
 * @param {number} postL - 后序左边界
 * @param {number} postR - 后序右边界
 */
function build(inL, inR, postL, postR) {
    if (inL > inR) {
        return;
    }

    // 后序遍历的最后一个节点是根节点
    const root = postOrder[postR];

    // 在中序遍历中找到根节点的位置
    const k = inOrder.indexOf(root);

    // 先输出根节点
    process.stdout.write(root);

    // 递归处理左子树
    build(inL, k - 1, postL, postL + k - inL - 1);

    // 递归处理右子树
    build(k + 1, inR, postL + k - inL, postR - 1);
}

function main() {
    const input = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
    inOrder = input[0];
    postOrder = input[1];

    build(0, inOrder.length - 1, 0, postOrder.length - 1);
    process.stdout.write('\n');
}

main();

关键代码讲解

1. 核心递归函数

void BuildPreorder(const std::string& in_order,
                   const std::string& post_order) {
    if (in_order.empty()) return;

    char root = post_order.back();           // 1. 后序最后一个是根
    size_t k = in_order.find(root);          // 2. 中序中找根位置

    std::cout << root;                       // 3. 先输出根

    BuildPreorder(in_order.substr(0, k),     // 4. 递归左子树
                  post_order.substr(0, k));

    BuildPreorder(in_order.substr(k + 1),   // 5. 递归右子树
                  post_order.substr(k, in_order.size() - k - 1));
}

2. 为什么后序最后一个是根？

后序遍历顺序：左 → 右 → 根
所以根总是在最后

3. 如何确定左右子树？

中序遍历：A D B E C
          左 根  右
找到 B 的位置，左边是左子树，右边是右子树

4. 子树范围计算

// 左子树：中序 [0, k)，后序 [0, k)
in_order.substr(0, k)
post_order.substr(0, k)

// 右子树：中序 [k+1, end)，后序 [k, end-1)
in_order.substr(k + 1)
post_order.substr(k, in_order.size() - k - 1)

复杂度分析

方法 时间复杂度 空间复杂度
递归分治 O(n²) 最坏情况 O(n)

说明：

  • 每次递归需要在中序遍历中查找根节点，使用 find() 时间复杂度为 O(n)
  • 递归深度最多为 n（树的高度）
  • 空间主要用于递归栈和字符串切分

易错点

  1. 根的确定：后序遍历的最后一个节点才是根，不要弄错顺序
  2. 字符串切分：
    • 左子树：in.substr(0, k) 和 post.substr(0, k)
    • 右子树：in.substr(k+1) 和 post.substr(k, len-k-1)
  3. 空树处理：递归前检查序列是否为空
  4. 字符输出：使用 print(root, end='') 避免自动换行

类似题目