【题解 | 二叉树】给定二叉树的后序遍历和中序遍历，求层序遍历结果

树的遍历

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数 N ( ≤ 30 ) N(≤30) N(≤30)，是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例：

4 1 6 3 5 7 2

解题

在后序遍历序列中，根节点总是在最后一个位置，而在中序遍历序列中，根节点将序列分为左右两部分，分别对应左子树和右子树。

因此，我们可以利用两个数组的信息，递归构建二叉树，然后再进行层序遍历。

Java

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

// 结点类
class TreeNode {
    int val;			// 值
    TreeNode left;		// 左孩子
    TreeNode right;		// 右孩子

    TreeNode(int x) {
        val = x;
    }
}

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] postOrder = new int[N];
        int[] inOrder = new int[N];
        for (int i = 0; i < N; i++) {
            postOrder[i] = scanner.nextInt();
        }
        for (int i = 0; i < N; i++) {
            inOrder[i] = scanner.nextInt();
        }
        // 根据后序遍历结果和前序遍历结果，构建二叉树
        TreeNode root = helper(postOrder, inOrder);
        // 层序遍历
        List<Integer> ans = levelOrderTraversal(root);
        // 输出结果
        for (int i = 0; i < ans.size(); i++) {
            System.out.print(ans.get(i));
            if (i < ans.size() - 1) {
                System.out.print(" ");
            }
        }
        scanner.close();
    }

    // 检查是否有某个序列为空
    private static TreeNode helper(int[] postOrder, int[] inOrder) {
        if (postOrder == null || inOrder == null || postOrder.length == 0 || inOrder.length == 0) {
            return null;
        }
        return buildTree(postOrder, 0, postOrder.length - 1, inOrder, 0, inOrder.length - 1);
    }

    /**
     * 构建二叉树
     * @param postOrder 	后序遍历结果
     * @param postStart 	后序遍历序列的起始位置
     * @param postEnd 		后序遍历序列的结束位置
     * @param inOrder 		中序遍历结果
     * @param inStart 		中序遍历序列的起始位置
     * @param inEnd 		中序遍历序列的结束位置
     * @return 构建的二叉树的根节点
     */
    private static TreeNode buildTree(int[] postOrder, int postStart, int postEnd, int[] inOrder, int inStart, int inEnd) {
    	// (0) 终止条件：此时没有结点了，返回空树
        if (postStart > postEnd || inStart > inEnd) {
            return null;
        }

        // (1) 先找到根结点：后序遍历的最后一个结点
        int rootVal = postOrder[postEnd];
        TreeNode root = new TreeNode(rootVal);

        // (2) 在中序遍历序列中找到根结点的位置
        int rootIndexInInOrder = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inOrder[i] == rootVal) {
                rootIndexInInOrder = i;
                break;
            }
        }

        // (3) 计算左子树的结点个数
        int leftTreeSize = rootIndexInInOrder - inStart;
        
        // (4) 递归构建左子树和右子树
        root.left = buildTree(postOrder, postStart, postStart + leftTreeSize - 1, inOrder, inStart, rootIndexInInOrder - 1);
        root.right = buildTree(postOrder, postStart + leftTreeSize, postEnd - 1, inOrder, rootIndexInInOrder + 1, inEnd);

        // (5) 返回根结点
        return root;
    }

    // 层序遍历二叉树
    private static List<Integer> levelOrderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        // 创建队列，用于层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        // 循环遍历队列中的结点
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            // 将当前结点的值加入结果列表
            result.add(node.val);
            if (node.left != null) {
                queue.offer(node.left); // 将左子结点加入队列
            }
            if (node.right != null) {
                queue.offer(node.right); // 将右子结点加入队列
            }
        }

        return result;
    }
}

C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 结点类
class TreeNode {
public:
    int val;        // 值
    TreeNode *left;     // 左孩子
    TreeNode *right;    // 右孩子

    TreeNode(int x) {
        val = x;
        left = nullptr;
        right = nullptr;
    }
};

// 构建二叉树
TreeNode* buildTree(vector<int>& postOrder, int postStart, int postEnd, vector<int>& inOrder, int inStart, int inEnd) {
    // 终止条件：此时没有结点了，返回空树
    if (postStart > postEnd || inStart > inEnd) {
        return nullptr;
    }

    // 先找到根结点：后序遍历的最后一个结点
    int rootVal = postOrder[postEnd];
    TreeNode* root = new TreeNode(rootVal);

    // 在中序遍历序列中找到根结点的位置
    int rootIndexInInOrder = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (inOrder[i] == rootVal) {
            rootIndexInInOrder = i;
            break;
        }
    }

    // 计算左子树的结点个数
    int leftTreeSize = rootIndexInInOrder - inStart;
    
    // 递归构建左子树和右子树
    root->left = buildTree(postOrder, postStart, postStart + leftTreeSize - 1, inOrder, inStart, rootIndexInInOrder - 1);
    root->right = buildTree(postOrder, postStart + leftTreeSize, postEnd - 1, inOrder, rootIndexInInOrder + 1, inEnd);

    // 返回根结点
    return root;
}

// 层序遍历二叉树
vector<int> levelOrderTraversal(TreeNode* root) {
    vector<int> result;
    if (root == nullptr) {
        return result;
    }

    // 创建队列，用于层序遍历
    queue<TreeNode*> q;
    q.push(root);

    // 循环遍历队列中的结点
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        // 将当前结点的值加入结果列表
        result.push_back(node->val);
        if (node->left != nullptr) {
            q.push(node->left); // 将左子结点加入队列
        }
        if (node->right != nullptr) {
            q.push(node->right); // 将右子结点加入队列
        }
    }

    return result;
}

int main() {
    int N;
    cin >> N;
    vector<int> postOrder(N);
    vector<int> inOrder(N);
    for (int i = 0; i < N; i++) {
        cin >> postOrder[i];
    }
    for (int i = 0; i < N; i++) {
        cin >> inOrder[i];
    }

    // 根据后序遍历结果和中序遍历结果，构建二叉树
    TreeNode* root = buildTree(postOrder, 0, N - 1, inOrder, 0, N - 1);
    // 层序遍历
    vector<int> ans = levelOrderTraversal(root);
    // 输出结果
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i];
        if (i < ans.size() - 1) {
            cout << " ";
        }
    }

    return 0;
}

测试链接：L2-006 树的遍历