剑指offer-JZ4

c++
本题是标准的二叉树重建任务，
利用递归的思路进行重构；
其中需要利用到前序和中序的特点，
前序pre：[root, left, right]
中序vin：[left, root, right];
因此对一个root节点的构建思路：
1---判断是否为空，边界条件
2---找到root的位置
遍历中序，判断vin[i] == pre[0];
得到 root_index
然后构建，左右：
---vin左: [0-------root_index-1]
---pre左：[1--------root_index]

---vin右：[root_index+1------end]
---pre右：[root_index+1------end]

递归构建
(pre左，vin左) (pre右，vin右)

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if (vin.size() == 0){
            return NULL;
        }
        TreeNode* root = new TreeNode(pre[0]); // defined  tree root
        vector<int> pre_left, pre_right, vin_left, vin_right; // difine and record tree infor 
        // find root index in vin
        int root_ind=0;
        for(int ind=0; ind<vin.size(); ind++){
            if (vin[ind] == pre[0]){
                root_ind=ind;
                break;
            }
        }
        // update right lefte
        for(int i=0; i<root_ind; i++){
            vin_left.push_back(vin[i]);
            pre_left.push_back(pre[i+1]);//the first is root, need plus 1
        }
        for(int i=root_ind+1; i<vin.size(); i++){
            vin_right.push_back(vin[i]);
            pre_right.push_back(pre[i]);
        }
        // 递归
        root->left = reConstructBinaryTree(pre_left, vin_left);
        root->right = reConstructBinaryTree(pre_right, vin_right);
        return root;
    }
};