题解 | #重建二叉树#

通过前序可以确定根，通过根和中序可以确定左子树和右子树，然后递归构建即可。

class Solution {
  public:
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        if (preOrder.empty() || vinOrder.empty()) return NULL;
        TreeNode* root = new TreeNode(preOrder[0]);
        int i;
        for (i = 0; i < vinOrder.size(); i++) {
            if (vinOrder[i] == root->val) break;
        }
        if (i) {
            vector<int> leftpre(preOrder.begin() + 1, preOrder.begin() + i + 1);
            vector<int> leftvin(vinOrder.begin(), vinOrder.begin() + i);
            root->left = reConstructBinaryTree(leftpre, leftvin);
        } else {
            root->left = NULL;
        }
        if (i < vinOrder.size() - 1) {
            vector<int> rightpre(preOrder.begin() + i + 1, preOrder.end());
            vector<int> rightvin(vinOrder.begin() + i + 1, vinOrder.end());
            root->right = reConstructBinaryTree(rightpre, rightvin);
        } else {
            root->right = NULL;
        }

        return root;
    }
};