牛客25665题：从层序和中序遍历重建二叉树

一、 问题背景

在二叉树相关算法题中，经常需要根据给定的遍历序列重建二叉树。这道牛客25665题要求我们根据输入的层序遍历和中序遍历序列重建二叉树，然后输出该树的叶子节点、前序遍历和后序遍历结果。

二、数据结构定义

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

这里定义了二叉树的节点结构，包含整数值val和左右子节点指针。

三、核心算法实现

3.1 二叉树重建函数

TreeNode* build(vector<int>& level, vector<int>& in, 
               int inStart, int inEnd, unordered_map<int,int>& pos) {
    if (level.empty() || inStart > inEnd) return nullptr;
    
    TreeNode* root = new TreeNode(level[0]);  // 创建当前根节点
    int idx = pos[level[0]];  // 获取根节点在中序中的位置
    
    // 分割左右子树的中序遍历范围
    vector<int> leftLevel, rightLevel;
    unordered_map<int,bool> inLeft;
    for (int i = inStart; i < idx; i++) 
        inLeft[in[i]] = true;  // 标记左子树节点
    
    // 分割层序遍历序列
    for (int i = 1; i < level.size(); i++) {
        if (inLeft.count(level[i])) 
            leftLevel.push_back(level[i]);  // 属于左子树
        else 
            rightLevel.push_back(level[i]);  // 属于右子树
    }
    
    // 递归构建左右子树
    root->left = build(leftLevel, in, inStart, idx-1, pos);
    root->right = build(rightLevel, in, idx+1, inEnd, pos);
    return root;
}

3.2 获取叶子节点函数

void getLeaves(TreeNode* root, vector<int>& res) {
    if (!root) return;
    if (!root->left && !root->right)  // 判断是否为叶子节点
        res.push_back(root->val);
    getLeaves(root->left, res);  // 递归左子树
    getLeaves(root->right, res);  // 递归右子树
}

3.3 遍历函数

void traversal(TreeNode* root, vector<int>& res, int type) {
    if (!root) return;
    if (type == 1) res.push_back(root->val); // 前序遍历
    traversal(root->left, res, type);
    traversal(root->right, res, type);
    if (type == 2) res.push_back(root->val); // 后序遍历
}

四、完整代码

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

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

TreeNode* build(vector<int>& level, vector<int>& in, 
               int inStart, int inEnd, unordered_map<int,int>& pos) {
    if (level.empty() || inStart > inEnd) return nullptr;
    
    TreeNode* root = new TreeNode(level[0]);
    int idx = pos[level[0]];
    
    vector<int> leftLevel, rightLevel;
    unordered_map<int,bool> inLeft;
    for (int i = inStart; i < idx; i++) 
        inLeft[in[i]] = true;
    
    for (int i = 1; i < level.size(); i++) {
        if (inLeft.count(level[i])) 
            leftLevel.push_back(level[i]);
        else 
            rightLevel.push_back(level[i]);
    }
    
    root->left = build(leftLevel, in, inStart, idx-1, pos);
    root->right = build(rightLevel, in, idx+1, inEnd, pos);
    return root;
}

void getLeaves(TreeNode* root, vector<int>& res) {
    if (!root) return;
    if (!root->left && !root->right) 
        res.push_back(root->val);
    getLeaves(root->left, res);
    getLeaves(root->right, res);
}

void traversal(TreeNode* root, vector<int>& res, int type) {
    if (!root) return;
    if (type == 1) res.push_back(root->val); // pre
    traversal(root->left, res, type);
    traversal(root->right, res, type);
    if (type == 2) res.push_back(root->val); // post
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    vector<int> level, in;
    string line;
    
    // 读取层序遍历
    getline(cin, line);
    size_t pos = 0;
    while ((pos = line.find(' ')) != string::npos) {
        level.push_back(stoi(line.substr(0, pos)));
        line.erase(0, pos + 1);
    }
    if (!line.empty()) level.push_back(stoi(line));
    
    // 读取中序遍历
    getline(cin, line);
    pos = 0;
    while ((pos = line.find(' ')) != string::npos) {
        in.push_back(stoi(line.substr(0, pos)));
        line.erase(0, pos + 1);
    }
    if (!line.empty()) in.push_back(stoi(line));
    
    // 建立中序位置索引
    unordered_map<int, int> inPos;
    for (int i = 0; i < in.size(); i++) 
        inPos[in[i]] = i;
    
    // 重建二叉树
    TreeNode* root = build(level, in, 0, in.size()-1, inPos);
    
    // 处理输出
    vector<int> leaves, pre, post;
    getLeaves(root, leaves);
    traversal(root, pre, 1);
    traversal(root, post, 2);
    
    // 输出结果
    for (int i = 0; i < leaves.size(); i++) 
        cout << (i ? " " : "") << leaves[i];
    cout << endl;
    
    for (int i = 0; i < pre.size(); i++) 
        cout << (i ? " " : "") << pre[i];
    cout << endl;
    
    for (int i = 0; i < post.size(); i++) 
        cout << (i ? " " : "") << post[i];
    cout << endl;
    
    return 0;
}

五、 总结

本文详细解析了如何根据层序和中序遍历重建二叉树的完整实现过程，包括：

1. 二叉树节点的定义

2. 核心的重建算法

3. 各种遍历方式的实现

4. 输入输出处理

5. 完整的代码实现

掌握这种方法对于理解二叉树的结构和各种遍历方式非常有帮助，是算法学习中的重要基础。