重建二叉树算法详解编程语言

/** 
 * 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* buildTree(vector<int>& preorder, vector<int>& inorder) { 
        if(preorder.size()==0||inorder.size()==0) 
            return nullptr; 
        int i_medpos=0; 
        while(i_medpos<inorder.size()) 
        { 
            if(inorder[i_medpos]==preorder[0]) 
                break; 
            i_medpos++; 
        } 
        TreeNode *root=new TreeNode(preorder[0]); 
        //前序数组中去掉根节点,中序数组中根节点的下标，在前序节点中此下标前的都是根节点的左子树 
        vector<int> left_pre(preorder.begin()+1,preorder.begin()+i_medpos+1); 
        vector<int> right_pre(preorder.begin()+i_medpos+1,preorder.end()); 
 
        vector<int> left_in(inorder.begin(),inorder.begin()+i_medpos); 
        //中序数组中去掉根节点 
        vector<int> right_in(inorder.begin()+i_medpos+1,inorder.end()); 
 
        root->left=buildTree(left_pre,left_in); 
        root->right=buildTree(right_pre,right_in); 
        return root; 
    } 
};