题解 | #重建二叉树#

遇到树的话，无脑递归就好了。

不断划分子区间（以根节点为界划分左右子树，递归到空节点时返回空）

注意左开右闭区间即可，此处用string的话更容易

/**
 * 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()) {
        return nullptr;
      }

      TreeNode *root = new TreeNode(pre[0]);

      auto p_vin = vin.begin();
      auto p_pre = pre.begin();

      while (*p_vin != *p_pre) {
        ++p_vin;
      }

      p_pre = p_pre + (p_vin - vin.begin()) + 1;

      root->left = reConstructBinaryTree(std::vector<int>(pre.begin() + 1, p_pre), std::vector<int>(vin.begin(), p_vin));
      root->right = reConstructBinaryTree(std::vector<int>(p_pre, pre.end()), std::vector<int>(p_vin + 1, vin.end()));

      return root;
    }
};