题解 | #重建二叉树#

二叉树重建，整体思想还是找到前序是：根左右，中序是左根右，然后递归调用即可。

 // 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) return new TreeNode(pre[0]);
        TreeNode* root = new TreeNode(pre[0]);
        pre.erase(pre.begin());
        int index = find(vin.begin(), vin.end(), root->val) - vin.begin();
        vin.erase(vin.begin() + index);
        vector<int> leftpre, leftvin;
        vector<int> rightpre, rightvin;
        if (index == 0)
        {
            root->left = NULL;

            rightpre.insert(rightpre.begin(),pre.begin() + index, pre.end());
            rightvin.insert(rightvin.begin(), vin.begin() + index, vin.end());
            root->right = reConstructBinaryTree(rightpre, rightvin);

        }
        else if (vin.size() - index  == 0)
        {
            leftpre.insert(leftpre.begin(), pre.begin(), pre.begin() + index);
            leftvin.insert(leftvin.begin(), vin.begin(), vin.begin() + index);
            root->left = reConstructBinaryTree(leftpre, leftvin);

            root->right = NULL;
        }
        else {
            //vector<int> leftpre,leftvin;
            leftpre.insert(leftpre.begin(), pre.begin(), pre.begin()+index);
            leftvin.insert(leftvin.begin(), vin.begin(), vin.begin()+index);
            root->left = reConstructBinaryTree(leftpre, leftvin);

            //vector<int> rightpre,rightvin;
            rightpre.insert(rightpre.begin(), pre.begin() + index, pre.end());
            rightvin.insert(rightvin.begin(), vin.begin() + index, vin.end());
            root->right = reConstructBinaryTree(rightpre, rightvin);
        }
        return root;


    }
};