题解 | #从前序和中序遍历构造二叉树#和上一题差不多

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */

class Solution {
  public:
    /**
     *
     * @param preorder int整型vector
     * @param inorder int整型vector
     * @return TreeNode类
     */
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() == 0) return nullptr;
        int rootvalue = preorder[0];
        TreeNode* root = new TreeNode(rootvalue);

        int temp;
        for (temp = 0; temp < inorder.size(); temp++) {
            if (inorder[temp] == rootvalue)
                break;
        }
        vector<int> leftinorder(inorder.begin(), inorder.begin() + temp);
        vector<int> rightinorder(inorder.begin() + temp + 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;
    }
};