题解 | #重建二叉树#

/**
 * 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) {
        int vl = 0, vr = vin.size()-1;
        auto res = build(pre, vin, 0, 0, vr);
        return res;
    }
    
//前序数组，中序数组，根节点在前序数组中的位置，当前子树区间在中序遍历中对应的左端点索引和右端点索引
    TreeNode* build(vector<int> &pre, vector<int> &vin,int pos, int vl, int vr) 
    {
        if(vl == vr)
        {
            TreeNode* lchild = new TreeNode(pre[pos]);
            return lchild;
        }
        if(vl > vr)
            return nullptr;
        
        TreeNode* root = new TreeNode(pre[pos]);
        
        int root_v_pos = vl;
        //找到根节点在中序遍历中的位置
        while(root_v_pos <= vr && vin[root_v_pos] != pre[pos]) ++root_v_pos;
        int length = root_v_pos - vl;
        int l_end = pos + length;
        
        root->left = build(pre,vin,pos+1,vl, root_v_pos-1);
        root->right = build(pre,vin,l_end+1, root_v_pos+1, vr);
        return root;
        
    }
};