题解 | #重建二叉树#

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

        int i = 0;
        for (i = 0; i < vinOrder.size(); i++) {
            if (vinOrder[i] == preOrder[0]) {
                break;
            }
        }
        // 前序左子树
        vector<int> preOrder1(preOrder.begin()+1, preOrder.begin()+i+1);
        // 前序右子树
        vector<int> preOrder2(preOrder.begin()+i+1, preOrder.end());
        // 中序左子树
        vector<int> vinOrder1(vinOrder.begin(), vinOrder.begin()+i);
        // 中序右子树
        vector<int> vinOrder2(vinOrder.begin()+i+1, vinOrder.end());
        auto root = new TreeNode(preOrder[0]);
        if (!vinOrder1.empty()) {
            root->left = reConstructBinaryTree(preOrder1, vinOrder1);
        }
        if (!vinOrder2.empty()) {
            root->right = reConstructBinaryTree(preOrder2, vinOrder2);
        }

        return root;
    }
};