二叉树的广度优先遍历 - 华为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));
        }

        // 根节点值
        char rootVal = postOrder.charAt(len - 1);
        TreeNode root = new TreeNode(rootVal);

        // 根节点在中序遍历中的索引位置, 此位置用于拆分左右子树
        int pos = inOrder.indexOf(rootVal);
        String leftPostOrder = postOrder.substring(0, pos);
        String rightPostOrder = postOrder.substring(pos, len - 1);

        String leftInOrder = inOrder.substring(0, pos);
        String rightInOrder = inOrder.substring(pos + 1);

        // 构造左右子树
        root.left = build(leftPostOrder, leftInOrder);
        root.right = build(rightPostOrder, rightInOrder);
        return root;
    }
}

Python

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def buildTree(self, postorder, inorder) -> TreeNode:
        """ 根据后续遍历和中序遍历构造树 """
        if not inorder:
            return None
        root = TreeNode(postorder[-1])
        pos = inorder.index(root.val)
        root.left = self.buildTree(postorder[:pos], inorder[:pos])
        root.right = self.buildTree(postorder[pos:-1], inorder[pos+1:])
        return root

    def levelOrder(self, root):
        """ 返回树的层次遍历结果 """
        res = []
        if not root:
            return res

        queue = [root]
        while queue:
            node = queue.pop(0)
            res.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return ''.join(res)


if __name__ == '__main__':
    s = Solution()
    postorder, inorder = map(list, input().split())
    root = s.buildTree(postorder, inorder)
    print(s.levelOrder(root))

C++

#include <bits/stdc++.h>
using namespace std;

struct TreeNode
{
    char      val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}
};

/* 构建树 */
TreeNode* buildTree(string postorder, string inorder)
{
    if (postorder.empty()) return nullptr;

    TreeNode* root = new TreeNode(postorder.back());
    postorder.pop_back();

    int pos = inorder.find(root->val);

    root->left  = buildTree(postorder.substr(0, pos), inorder.substr(0, pos));
    root->right = buildTree(postorder.substr(pos), inorder.substr(pos + 1));

    return root;
}

/* 返回树的层次遍历结果 */
string levelOrder(TreeNode* root)
{
    string           res;
    queue<TreeNode*> q;
    if (root) q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        res += node->val;
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
    return res;
}

int main()
{
    string postorder, inorder;
    cin >> postorder >> inorder;
    TreeNode* root = buildTree(postorder, inorder);
    cout << levelOrder(root) << endl;
    return 0;
}    

相关练习题

希望这个专栏不仅能帮您成功通过华为机试，还能让您熟练掌握算法。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏