算法——层序遍历和中序遍历构造二叉树

晴问

1. #include <iostream>
2. #include <vector>
3. #include <queue>
4. #include <unordered_map>
6. using namespace std;
8. struct TreeNode {
9.     int data;
10.     TreeNode *left;
11.     TreeNode *right;
13.     TreeNode(int data) : data(data), left(nullptr), right(nullptr) {}
14. };
16. // 函数用于根据层序和中序遍历结果重建二叉树
17. TreeNode* buildTree(vector<int>& levelOrder, vector<int>& inOrder, int inStart, int inEnd, int levelStart, int levelEnd) {
18.     if (inStart > inEnd) return nullptr;
20.     TreeNode* root = new TreeNode(levelOrder[levelStart]);
22.     int inRootIndex = inStart;
23.     while (inOrder[inRootIndex] != levelOrder[levelStart]) {
24.         inRootIndex++;
25.     }
27.     int leftTreeSize = inRootIndex - inStart;
29.     root->left = buildTree(levelOrder, inOrder, inStart, inRootIndex - 1, levelStart + 1, levelStart + leftTreeSize);
30.     root->right = buildTree(levelOrder, inOrder, inRootIndex + 1, inEnd, levelStart + leftTreeSize + 1, levelEnd);
32.     return root;
33. }
35. // 先序遍历函数
36. void preOrder(TreeNode* root) {
37.     if (root == nullptr) return;
38.     cout << root->data << " ";
39.     preOrder(root->left);
40.     preOrder(root->right);
41. }
43. int main() {
44.     int n;
45.     cin >> n;
46.     vector<int> levelOrder(n), inOrder(n);
48.     for (int i = 0; i < n; ++i) {
49.         cin >> levelOrder[i];
50.     }
51.     for (int i = 0; i < n; ++i) {
52.         cin >> inOrder[i];
53.     }
55.     TreeNode* root = buildTree(levelOrder, inOrder, 0, n - 1, 0, n - 1);
56.     preOrder(root);
58.     return 0;
59. }

复制代码