树

1.重构二叉树

题解：相对于跟节点对位置，可以分为：

• 前序遍历(根左右)
• 中序遍历(左根右)
• 后续遍历(左右根)

一般题目会给定前序遍历(或后序遍历)、中序遍历，让你重构二叉树，输出另一种遍历。如果没有给定中序遍历则无法重构二叉树。
思路：首先在前序(第一个元素)或者后续(最后一个元素)中找到根节点，然后遍历中序，找到根节点，分别递归重建左子树和右子树即可。

https://www.cnblogs.com/daimadebanyungong/p/4919665.html

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in)
    {
        //树：可以由根节点表示。
        TreeNode *tree = reBulidBinaryTree(pre,0,pre.size()-1,in,0,in.size()-1);
        return tree;
    }
public:
   struct TreeNode* reBulidBinaryTree(vector<int> pre,int pre_start,int pre_end,vector<int> in,int in_start,int in_end)
   {
       if(pre_start > pre_end || in_start > in_end)
       {
           return NULL;
       }

        //1. 前序遍历中：第一个元素是根节点
       TreeNode *root = new TreeNode(pre.at(pre_start));
        //2. 遍历中序：找到根节点所在位置。
       for(i = in_start; i <= in_end; i++)
       {
           if(in.at(i) == pre.at(pre_start))
           {  //find the position where in order traverse value is the root of the tree
                    //递归：重构左子树；其中：i - in_start：表示左子树有多少个原属
                    root->left = reBulidBinaryTree(pre, pre_start+1, pre_start+i-in_start, in, in_start, i-1);
                    //递归：重构右子树
                    root->right = reBulidBinaryTree(pre, pre_start+i-in_start+1 ,pre_end, in, i+1, in_end);
                    break;
           }
       }
       return root;
   }
};