题解 | #JZ4 重建二叉树#

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size() == 0){
            return NULL;
        }

        if(pre.size() == 1){
             TreeNode* root = (TreeNode* )malloc(sizeof(struct TreeNode));
             root->val = pre[0];
             root->left = NULL;
             root->right = NULL;
             return root;
        }
        int rootValue = pre[0];
        TreeNode* root = (TreeNode* )malloc(sizeof(struct TreeNode));
        root->val = rootValue;
        int rootValuaInVinPos = -1;
        int leftTreeSize;
        int rightTreeSize;
        for(int i=0;i<vin.size();i++){
            if(vin[i] == rootValue){
                leftTreeSize = i;
                break;
            }
        }
        rightTreeSize = pre.size() - 1 - leftTreeSize;
        vector<int> leftPre;
        vector<int> leftVin;
        for(int i=0;i<leftTreeSize;i++){
            leftPre.push_back(pre[i+1]);
        }
        for(int i=0;i<leftTreeSize;i++){
            leftVin.push_back(vin[i]);
        }
        TreeNode* leftTree = reConstructBinaryTree(leftPre,leftVin);

        vector<int> rightPre;
        vector<int> rightVin;
        for(int i=0;i<rightTreeSize;i++){
            rightPre.push_back(pre[i+1+leftTreeSize]);
        }
        for(int i=0;i<rightTreeSize;i++){
            rightVin.push_back(vin[i+1+leftTreeSize]);
        }
        TreeNode* rightTree = reConstructBinaryTree(rightPre,rightVin);

        root->left = leftTree;
        root->right = rightTree;
        return root;
    }
};