算法——层序遍历和中序遍历构造二叉树
晴问#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);
int inRootIndex = inStart;
while (inOrder != levelOrder) {
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;
}
for (int i = 0; i < n; ++i) {
cin >> inOrder;
}
TreeNode* root = buildTree(levelOrder, inOrder, 0, n - 1, 0, n - 1);
preOrder(root);
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]