二叉树重构cyuyan写

二叉树重构可以使用递归的方式来实现。具体步骤如下：

1. 定义一个结构体来表示二叉树节点，包含节点值和左右子树两个指针。

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

2. 根据给定的前序遍历和中序遍历序列来重构二叉树。在前序遍历序列中，第一个元素为根节点，根据这个节点在中序遍历序列中找到根节点的位置，然后递归地重构左右子树。

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 rootIdx = find(inorder.begin(), inorder.end(), rootVal) - inorder.begin();
    vector<int> leftInorder(inorder.begin(), inorder.begin() + rootIdx);
    vector<int> rightInorder(inorder.begin() + rootIdx + 1, inorder.end());
    vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + 1 + leftInorder.size());
    vector<int> rightPreorder(preorder.begin() + 1 + leftInorder.size(), preorder.end());
    root->left = buildTree(leftPreorder, leftInorder);
    root->right = buildTree(rightPreorder, rightInorder);
    return root;
}

3. 在主函数中调用 buildTree() 函数，传入前序遍历和中序遍历序列，即可得到重构后的二叉树。

int main() {
    vector<int> preorder = {1, 2, 4, 5, 3, 6};
    vector<int> inorder = {4, 2, 5, 1, 3, 6};
    TreeNode* root = buildTree(preorder, inorder);
    // do something with the reconstructed binary tree
    return 0;
}