二叉树层次遍历和中序遍历完整代码

以下是C++实现二叉树层次遍历和中序遍历的完整代码：

#include <iostream>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 生成二叉树
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.empty() || inorder.empty()) {
        return NULL;
    }
    int rootVal = preorder[0];
    TreeNode* root = new TreeNode(rootVal);
    int rootIndex = 0;
    for (int i = 0; i < inorder.size(); i++) {
        if (inorder[i] == rootVal) {
            rootIndex = i;
            break;
        }
    }
    vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + rootIndex + 1);
    vector<int> rightPreorder(preorder.begin() + rootIndex + 1, preorder.end());
    vector<int> leftInorder(inorder.begin(), inorder.begin() + rootIndex);
    vector<int> rightInorder(inorder.begin() + rootIndex + 1, inorder.end());
    root->left = buildTree(leftPreorder, leftInorder);
    root->right = buildTree(rightPreorder, rightInorder);
    return root;
}

// 层次遍历
void levelOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();
            cout << node->val << " ";
            if (node->left != NULL) {
                q.push(node->left);
            }
            if (node->right != NULL) {
                q.push(node->right);            }
        }
    }
}

// 中序遍历
void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

int main() {
    vector<int> preorder = { 3,9,20,15,7 };
    vector<int> inorder = { 9,3,15,20,7 };
    TreeNode* root = buildTree(preorder, inorder);
    cout << "层次遍历结果：";
    levelOrder(root);
    cout << endl;
    cout << "中序遍历结果：";
    inorderTraversal(root);
    cout << endl;
    return 0;
}