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

9小时前牛客题解24

一、问题背景

在二叉树相关算法题中，经常需要根据给定的遍历序列重建二叉树。这道牛客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;
}