【华为OD机试真题】C卷-二叉树的广度优先遍历（JAVA）

一、题目描述

【华为OD机试真题】C卷-二叉树的广度优先遍历（JAVA）

题目描述：

有一棵二叉树，每个节点由一个大写字母标识(最多26个节点）。
现有两组字母，分别表示后序遍历（左孩子->右孩子->父节点）和中序遍历（左孩子->父节点->右孩子）的结果，请你输出层序遍历的结果。

二、输入输出

输入描述：
每个输入文件一行，第一个字符串表示后序遍历结果，第二个字符串表示中序遍历结果。（每串只包含大写字母）
中间用单空格分隔。

输出描述：
输出仅一行，表示层序遍历的结果，结尾换行。

三、参考示例

用例
输入：
CBEFDA CBAEDF
输出：
ABDCEF

四、解题思路

1. 定义两个方法，splitLR用于分割左右子树，getResult用于获取最终结果。
2. 在splitLR方法中，根据后序遍历和中序遍历的特点，找到根节点，划分左右子树，并将子树加入队列。
3. 在getResult方法中，先处理根节点，然后遍历队列，依次处理子树，直到队列为空。
4. 最后将结果列表中的字符连接起来，返回最终结果。

五、参考代码

/*
 * @Author: mgc
 * @Date: 2024-02-02 17:47:00
 * @LastEditors: Do not edit
 * @LastEditTime: 2024-02-02 17:48:55
 */

// import java.util.*;
// import java.util.HashMap;
// import java.util.Scanner;
// import java.util.regex.Matcher;
// import java.util.stream.Stream;
// import java.util.regex.Pattern;
// import java.util.stream.Collectors;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取输入的后序遍历和中序遍历结果
        String post = sc.next();
        String mid = sc.next();

        // 输出结果
        System.out.println(getResult(post, mid));
    }

    // 获取最终结果的方法
    public static String getResult(String post, String mid) {
        LinkedList<String[]> queue = new LinkedList<>();
        ArrayList<Character> result = new ArrayList<>();

        // 划分左右子树
        splitLR(post, mid, queue, result);

        // 处理队列中的子树
        while (!queue.isEmpty()) {
            String[] tmp = queue.removeFirst();
            splitLR(tmp[0], tmp[1], queue, result);
        }

        // 构建最终结果字符串
        StringBuilder sb = new StringBuilder();
        for (Character c : result) {
            sb.append(c);
        }
        return sb.toString();
    }

    // 划分左右子树的方法
    public static void splitLR(String post, String mid, LinkedList<String[]> queue,
                               ArrayList<Character> result) {
        char rootElement = post.charAt(post.length() - 1);
        result.add(rootElement);

        int rootIndex = mid.indexOf(rootElement);
        int leftLength = rootIndex;

        // 划分左子树
        if (leftLength > 0) {
            String leftPost = post.substring(0, leftLength);
            String leftMid = mid.substring(0, rootIndex);
            queue.addLast(new String[] {leftPost, leftMid});
        }

        // 划分右子树
        if (post.length() - 1 - leftLength > 0) {
            String rightPost = post.substring(leftLength, post.length() - 1);
            String rightMid = mid.substring(rootIndex + 1);
            queue.addLast(new String[] {rightPost, rightMid});
        }
    }
}

六、华为OD机试真题汇总目录

    【华为OD机试】真题汇总A+B+C+D券（Python实现）

    【华为OD机试】真题汇总A+B+C+D卷（JAVA实现）

    【华为OD机试】真题汇总A+B+C+D卷（C++实现）