二叉树的广度优先遍历 - 华为OD统一考试(D卷)

OD统一考试（D卷）

分值： 200分

题解： Java / Python / C++

题目描述

有一棵二叉树，每个节点由一个大写字母标识(最多26个节点）。

现有两组字母，分别表示后序遍历（左孩子->右孩子->父节点）和中序遍历（左孩子->父节点->右孩子）的结果，请输出层次遍历的结果。

输入描述

输入为两个字符串，分别是二叉树的后续遍历和中序遍历结果。

输出描述

输出二叉树的层次遍历结果。

示例1

输入：
CBEFDA CBAEDF

输出：
ABDCEF

说明：
二叉树为：
    A
   / \
  B   D
 /   / \
C   E   F

题解

• 题目类型: 该题目是关于树的构建和遍历的问题。
• 解题思路:
  • 首先需要根据给定的后序遍历和中序遍历构建二叉树。
  • 构建二叉树的过程可以通过递归实现。在递归中，根据后序遍历的最后一个节点确定根节点，在中序遍历中找到对应的根节点位置，从而分隔左右子树。
  • 构建好二叉树后，再进行层次遍历。层次遍历可以利用队列进行，从根节点开始，将每一层的节点依次加入队列，并输出值，直至队列为空。
• 代码描述:
  • Java代码中，通过递归实现了树的构建，然后利用队列进行层次遍历。
  • Python代码和C++代码实现了同样的功能，Python代码利用了列表模拟队列，而C++代码使用了STL中的queue。
• 时间复杂度:
  • 树的构建时间复杂度为O(N)，其中N为节点数。
  • 层次遍历时间复杂度为O(N)。
• 空间复杂度:
  • 递归过程中的栈空间复杂度为O(N)，用于树的构建。
  • 层次遍历中的队列空间复杂度为O(N)。

Java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        String postOrder = in.next(), inOrder = in.next();
        Solution solution = new Solution();
        TreeNode root = solution.build(postOrder, inOrder);

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        StringBuilder rs = new StringBuilder();
        while (!q.isEmpty()) {
            TreeNode poll = q.poll();
            rs.append(poll.val);

            if (poll.left != null) q.offer(poll.left);
            if (poll.right != null) q.offer(poll.right);
        }
        System.out.println(rs.toString());
    }
}


class TreeNode {
    public char val;
    public TreeNode left, right;

    public TreeNode(char val) {
        this.val = val;
    }
}

class Solution {
    
    /**
     * 构建树
     *
     * @param postOrder 后序遍历
     * @param inOrder   中序遍历
     * @return
     */
    public TreeNode build(String postOrder, String inOrder) {
        int len = postOrder.length();
        if (len == 0) {
            return null;
        } else if (len == 1) {
            return new TreeNode(postOrder.charAt(0));
        }

        // 根节点值