中序遍历求完美二叉树c++

Question

请问给定一个满二叉树的中序遍历如何求改二叉树？（层次之间输出要换行，代码c++）

Answer 1

#include <iostream>
#include <vector>
#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>& inorder, int level) {
    if (inorder.empty()) {
        return NULL;
    }
    queue<TreeNode*> q;
    int n = inorder.size();
    int idx = 0;
    TreeNode* root = new TreeNode(1);
    q.push(root);
    level--;
    while (!q.empty() && level > 0) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode* cur = q.front();
            q.pop();
            cur->left = new TreeNode(++idx);
            q.push(cur->left);
            if (idx == n) {
                return root;
            }
            cur->right = new TreeNode(++idx);
            q.push(cur->right);
            if (idx == n) {
                return root;
            }
        }
        level--;
    }
    int i = 0;
    int j = 0;
    while (i < n && j < level) {
        TreeNode* cur = q.front();
        q.pop();
        cur->left = new TreeNode(inorder[i++]);
        q.push(cur->left);
        cur->right = new TreeNode(inorder[i++]);
        q.push(cur->right);
        j++;
    }
    return root;
}

void printTree(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* cur = q.front();
            q.pop();
            cout << cur->val << " ";
            if (cur->left != NULL) {
                q.push(cur->left);
            }
            if (cur->right != NULL) {
                q.push(cur->right);
            }
        }
        cout << endl;
    }
}

int main() {
    vector<int> inorder = {1, 2, 3, 4, 5, 6, 7};
    int level = 3;
    TreeNode* root = buildTree(inorder, level);
    printTree(root);
    return 0;
}