题解 | #重建二叉树#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param preOrder int整型vector 
     * @param vinOrder int整型vector 
     * @return TreeNode类
     */
   TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
    // 如果两个序列都为空，返回空指针
    if (preOrder.empty() && vinOrder.empty()) return nullptr;

    // 创建根节点，其值为先序遍历的第一个元素
    TreeNode* root = new TreeNode(preOrder[0]);

    // 在中序遍历中找到根节点的位置
    auto it = find(vinOrder.begin(), vinOrder.end(), preOrder[0]);

    // 分割中序遍历序列得到左子树和右子树的元素
    vector<int> vin_new(vinOrder.begin(), it); // 左子树在中序遍历中的元素
    vector<int> vin_old(it + 1, vinOrder.end()); // 右子树在中序遍历中的元素

    // 根据左子树的元素数量分割先序遍历序列
    vector<int> pre_new(preOrder.begin() + 1, preOrder.begin() + vin_new.size() + 1); // 左子树在先序遍历中的元素
    vector<int> pre_old(preOrder.begin() + vin_new.size() + 1, preOrder.end()); // 右子树在先序遍历中的元素

    // 递归地构造左子树和右子树
    root->left = reConstructBinaryTree(pre_new, vin_new);
    root->right = reConstructBinaryTree(pre_old, vin_old);

    // 返回根节点
    return root;
    }
};