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

晴问

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>using namespace std;struct TreeNode {int data;TreeNode *left;TreeNode *right;TreeNode(int data) : data(data), left(nullptr), right(nullptr) {}
};// 函数用于根据层序和中序遍历结果重建二叉树
TreeNode* buildTree(vector<int>& levelOrder, vector<int>& inOrder, int inStart, int inEnd, int levelStart, int levelEnd) {if (inStart > inEnd) return nullptr;TreeNode* root = new TreeNode(levelOrder[levelStart]);int inRootIndex = inStart;while (inOrder[inRootIndex] != levelOrder[levelStart]) {inRootIndex++;}int leftTreeSize = inRootIndex - inStart;root->left = buildTree(levelOrder, inOrder, inStart, inRootIndex - 1, levelStart + 1, levelStart + leftTreeSize);root->right = buildTree(levelOrder, inOrder, inRootIndex + 1, inEnd, levelStart + leftTreeSize + 1, levelEnd);return root;
}// 先序遍历函数
void preOrder(TreeNode* root) {if (root == nullptr) return;cout << root->data << " ";preOrder(root->left);preOrder(root->right);
}int main() {int n;cin >> n;vector<int> levelOrder(n), inOrder(n);for (int i = 0; i < n; ++i) {cin >> levelOrder[i];}for (int i = 0; i < n; ++i) {cin >> inOrder[i];}TreeNode* root = buildTree(levelOrder, inOrder, 0, n - 1, 0, n - 1);preOrder(root);return 0;
}