题解 | #重建二叉树#

/**
 * 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* Build(TreeNode* root,vector<int> pre,vector<int> vin,int s1,int e1,int s2,int e2){
        if(s1 > e1 || s2 > e2)
            return NULL;
        if(root == NULL){
            root = (TreeNode*)malloc(sizeof(TreeNode));
            root->val = pre[s1];
            root->left = NULL;
            root->right = NULL;
        }
        int num = pre[s1],pos = 0;
        for(int i = s2;i <= e2;++i){
            if(vin[i] == num){
                pos = i;
                break;
            }
        }
        root->left = Build(root->left,pre,vin,s1 + 1,s1 + pos - s2,s2,pos - 1);
        root->right = Build(root->right,pre,vin,s1 + pos - s2 + 1,e1,pos + 1,e2);
        return root;
    }
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        TreeNode* root = NULL;
        if(pre.size() == 0)
            return root;
        return Build(root,pre,vin,0,pre.size() - 1,0,vin.size() - 1);
    }
};