题解 | #JZ7 重建二叉树#

//递归

/**
 * 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.empty() || vin.empty()) return nullptr;    //遍历为空则返回空
        
        TreeNode * head = new TreeNode(pre[0]);        //新建根节点
        
        auto vinIt = find(vin.begin(), vin.end(), pre[0]);    //在中序遍历中找到根节点
        int leftCnt = vinIt-vin.begin();        //根节点的左子树节点个数
        
        vector<int> leftVin(vin.begin(), vinIt);    //根节点左边为左子树
        vector<int> rightVin(vinIt+1, vin.end());    //根节点右边为右子树，跳过根节点
        vector<int> leftPre(pre.begin()+1, pre.begin()+1+leftCnt);    //跳过根节点，左子树拷贝
        vector<int> rightPre(pre.begin()+1+leftCnt, pre.end());    //跳过左子树，右子树拷贝
        
        head->left = reConstructBinaryTree(leftPre, leftVin);
        head->right = reConstructBinaryTree(rightPre, rightVin);
        
        return head;
    }
};