题解 | #重建二叉树#

深度优先搜索DFS，先重建根节点，在判断左节点是否存在，如果存在就重建并将左节点视为左树的根节点，依次类推，有点像先序遍历， 还好这道题的要求是没有重复数字，如果有，答案就不止一个了。

/**
 * 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;
        int head = pre[0];
        int index = find(vin.begin(), vin.end(), head) - vin.begin();
        TreeNode* p = new TreeNode(head);
        vector<int> leftpre(pre.begin()+1,pre.begin()+index+1);
        vector<int> leftvin(vin.begin(), vin.begin()+index);
        vector<int> rightpre(pre.begin()+index+1,pre.end());
        vector<int> rightvin(vin.begin()+index+1,vin.end());
        if(!leftpre.empty() && !leftvin.empty())p->left = reConstructBinaryTree(leftpre, leftvin);
        if(!rightpre.empty() && !rightvin.empty())p->right = reConstructBinaryTree(rightpre, rightvin);
        return p;
    }
};