牛客25665题详解：二叉树重建与三种遍历实现

胡志明t

一、题目解读

牛客25665题要求根据给定的层序遍历和中序遍历序列重建二叉树，并输出：

    1.所有叶子节点（从左到右）

    2.前序遍历序列

    3.后序遍历序列

二、解题思路

1.代码采用分治算法实现：

    使用哈希表记录中序遍历位置

2.递归构建二叉树：

    每次取层序**元素作为根节点

    根据中序分割左右子树

    筛选层序中属于左/右子树的元素

3.三种遍历实现：

    前序：根→左→右

    后序：左→右→根

    叶子节点：左右子节点均为空

三、解题步骤

1.读取输入数据（层序+中序）

2.建立中序遍历位置索引

3.递归构建二叉树

4.获取叶子节点和前序/后序遍历结果

5.格式化输出结果

四、完整代码实现C++

1. struct TreeNode {
   
2.     int val;
   
3.     TreeNode *left, *right;
   
4.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
   
5. };
   
6. 
   
7. TreeNode* build(vector<int>& level, vector<int>& in,
   
8.                int inStart, int inEnd, unordered_map<int,int>& pos) {
   
9.     if (level.empty() || inStart > inEnd) return nullptr;
   
10.    
    
11.     TreeNode* root = new TreeNode(level[0]);
    
12.     int idx = pos[level[0]];
    
13.    
    
14.     vector<int> leftLevel, rightLevel;
    
15.     unordered_map<int,bool> inLeft;
    
16.     for (int i = inStart; i < idx; i++)
    
17.         inLeft[in[i]] = true;
    
18.    
    
19.     for (int i = 1; i < level.size(); i++) {
    
20.         if (inLeft.count(level[i]))
    
21.             leftLevel.push_back(level[i]);
    
22.         else
    
23.             rightLevel.push_back(level[i]);
    
24.     }
    
25.    
    
26.     root->left = build(leftLevel, in, inStart, idx-1, pos);
    
27.     root->right = build(rightLevel, in, idx+1, inEnd, pos);
    
28.     return root;
    
29. }
    
30. 
    
31. void getLeaves(TreeNode* root, vector<int>& res) {
    
32.     if (!root) return;
    
33.     if (!root->left && !root->right)
    
34.         res.push_back(root->val);
    
35.     getLeaves(root->left, res);
    
36.     getLeaves(root->right, res);
    
37. }
    
38. 
    
39. void traversal(TreeNode* root, vector<int>& res, int type) {
    
40.     if (!root) return;
    
41.     if (type == 1) res.push_back(root->val); // pre
    
42.     traversal(root->left, res, type);
    
43.     traversal(root->right, res, type);
    
44.     if (type == 2) res.push_back(root->val); // post
    
45. }
    
46. 
    
47. int main() {
    
48.     ios::sync_with_stdio(false);
    
49.     cin.tie(0);
    
50.    
    
51.     vector<int> level, in;
    
52.     string line;
    
53.    
    
54.     // 读取层序遍历
    
55.     getline(cin, line);
    
56.     size_t pos = 0;
    
57.     while ((pos = line.find(' ')) != string::npos) {
    
58.         level.push_back(stoi(line.substr(0, pos)));
    
59.         line.erase(0, pos + 1);
    
60.     }
    
61.     if (!line.empty()) level.push_back(stoi(line));
    
62.    
    
63.     // 读取中序遍历
    
64.     getline(cin, line);
    
65.     pos = 0;
    
66.     while ((pos = line.find(' ')) != string::npos) {
    
67.         in.push_back(stoi(line.substr(0, pos)));
    
68.         line.erase(0, pos + 1);
    
69.     }
    
70.     if (!line.empty()) in.push_back(stoi(line));
    
71.    
    
72.     // 建立中序位置索引
    
73.     unordered_map<int, int> inPos;
    
74.     for (int i = 0; i < in.size(); i++)
    
75.         inPos[in[i]] = i;
    
76.    
    
77.     // 重建二叉树
    
78.     TreeNode* root = build(level, in, 0, in.size()-1, inPos);
    
79.    
    
80.     // 处理输出
    
81.     vector<int> leaves, pre, post;
    
82.     getLeaves(root, leaves);
    
83.     traversal(root, pre, 1);
    
84.     traversal(root, post, 2);
    
85.    
    
86.     // 输出结果
    
87.     for (int i = 0; i < leaves.size(); i++)
    
88.         cout << (i ? " " : "") << leaves[i];
    
89.     cout << endl;
    
90.    
    
91.     for (int i = 0; i < pre.size(); i++)
    
92.         cout << (i ? " " : "") << pre[i];
    
93.     cout << endl;
    
94.    
    
95.     for (int i = 0; i < post.size(); i++)
    
96.         cout << (i ? " " : "") << post[i];
    
97.     cout << endl;
    
98.    
    
99.     return 0;
    
100. }

复制代码

五、总结

本文详解了通过层序+中序重建二叉树的算法，实现了三种遍历方式。该解法时间复杂度O(n²)，空间复杂度O(n)，适合笔试面试准备。关键点在于递归分割中序序列和筛选层序子序列。

参考：牛客题解