重建二叉树（前序+中序配合）

解题思路：

• 先按照前序遍历和中序遍历的特点，来模拟重建二叉树
• 在模拟的过程中，看看是否符合递归的三个特点：
  • 这个问题能不能拆分成若干个子问题，子问题解决了，那么这个问题就解决了
  • 所有子问题的求解方法是不是和大问题的求解方法是一样的
  • 是不是存在知道结果的最小子问题
• 递归编写：终结条件+递归公式
  
  preorder:
  左子树头：PreLeft+1
  左子树尾：PreLeft+Index-InLeft
  右子树头：PreLeft+Index-InLeft+1
  右子树尾：PreRight
  inorder:
  左子树头：InLeft
  左子树尾：Index-1
  右子树头：Index+1
  右子树尾：InRight

  /**
   * Definition for a binary tree node.
   * struct TreeNode {
   *     int val;
   *     TreeNode *left;
   *     TreeNode *right;
   *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
   * };
   */
  class Solution {
  public:
      TreeNode* buildTreedfs(map<int,int>& mp,
                    vector<int>& preorder, vector<int>& inorder,
                    int PreLeft,int PreRight,int InLeft,int InRight)        
      {
          if(InLeft>InRight || PreLeft>PreRight) return nullptr;
          int rootval=preorder[PreLeft];
          TreeNode* root=new TreeNode(rootval);//前序开头一定是根节点
          int Index=mp[rootval];//找中序遍历找到前序遍历中对应根节点位置的值
          root->left=buildTreedfs(mp,preorder,inorder,PreLeft+1,PreLeft+Index-InLeft,InLeft,Index-1);
          root->right=buildTreedfs(mp,preorder,inorder,PreLeft+Index-InLeft+1,PreRight,Index+1,InRight);
          return root;
      }
      TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
          map<int,int> mp;//如果是vector容器，想赋值必须申请空间
          int PreLeft=0,PreRight=preorder.size()-1;
          int InLeft=0,InRight=inorder.size()-1;
          for(int i=0;i<inorder.size();i++)//标定中序遍历的位置
              mp[inorder[i]]=i;
          return buildTreedfs(mp,preorder,inorder,PreLeft,PreRight,InLeft,InRight);
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32