题解 | #重建二叉树#

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        if (preOrder.empty() || vinOrder.empty()) return nullptr;

        //前序的第一个是根节点
        int rootVal = preOrder[0];
        TreeNode* pRoot = new TreeNode(rootVal);

        // 在中序遍历中找到根节点的位置
        auto it = std::find(vinOrder.begin(), vinOrder.end(), rootVal);
        int rootIndex = it - vinOrder.begin();

        // 构建左子树的前序和中序遍历序列
        std::vector<int> leftPreOrder(preOrder.begin() + 1,
                                      preOrder.begin() + 1 + rootIndex);
        std::vector<int> leftVinOrder(vinOrder.begin(), vinOrder.begin() + rootIndex);

        // 构建右子树的前序和中序遍历序列
        std::vector<int> rightPreOrder(preOrder.begin() + 1 + rootIndex,
                                       preOrder.end());
        std::vector<int> rightVinOrder(vinOrder.begin() + rootIndex + 1,
                                       vinOrder.end());

        // 递归构建左右子树
        pRoot->left = reConstructBinaryTree(leftPreOrder, leftVinOrder);
        pRoot->right = reConstructBinaryTree(rightPreOrder, rightVinOrder);

        return pRoot;
    }
};