题解 | #重建二叉树#

根据前序和中序来重建二叉树

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param preOrder int整型一维数组 
 * @param preOrderLen int preOrder数组长度
 * @param vinOrder int整型一维数组 
 * @param vinOrderLen int vinOrder数组长度
 * @return TreeNode类
 */
 #define Maxsize 2001
//前序遍历思想
struct TreeNode* reConstructBinaryTree(int* preOrder, int preOrderLen, int* vinOrder, int vinOrderLen ) {
    if(vinOrderLen==0) return NULL;
    //构建结点
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root ->val = preOrder[0];
    //构建左右数组
    int* pre_left = (int *)malloc(sizeof(int)*Maxsize);
    int* pre_right = (int *)malloc(sizeof(int)*Maxsize);
    int* vin_left = (int *)malloc(sizeof(int)*Maxsize);
    int* vin_right = (int *)malloc(sizeof(int)*Maxsize);
    int locat = 0;
    for(int i = 0;i<vinOrderLen;i++){
        if(vinOrder[i] == preOrder[0]){
            locat = i;
            break;
        }
    }
    for(int i = 0;i<locat;i++){
        vin_left[i] = vinOrder[i];
        pre_left[i] = preOrder[i+1];
    }
    int j = 0;
    for(int i = locat+1;i<vinOrderLen;i++){
        vin_right[j] = vinOrder[i];
        pre_right[j] = preOrder[i];
        j++;
    }
    //左节点
    root->left = reConstructBinaryTree(pre_left,locat,vin_left,locat);
    //右节点
    root->right = reConstructBinaryTree(pre_right,vinOrderLen-locat-1,vin_right,vinOrderLen-locat-1);
    return root;
}