题解 | #重建二叉树#

/**
 * 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类
 */
#include <stdio.h>
int searchArr(int *Arr, int ArrLen, int p) {
    int i;
    for(i=0;i<ArrLen;i++) {
        if(p==Arr[i])
            return i;
    }
    return -1;
}
struct TreeNode* reConstructBinaryTree(int* preOrder, int preOrderLen, int* vinOrder, int vinOrderLen ) {
    struct TreeNode* res;
    int leftTreeLen, rightTreeLen;
    if(!preOrderLen)
        return NULL;

    res = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    res->val = preOrder[0];
    
    leftTreeLen = searchArr(vinOrder, vinOrderLen, preOrder[0]);
    rightTreeLen = preOrderLen-1-leftTreeLen;
    res->left = reConstructBinaryTree(preOrder+1, leftTreeLen, vinOrder, leftTreeLen);
    res->right = reConstructBinaryTree(preOrder+1+leftTreeLen, rightTreeLen, vinOrder+leftTreeLen+1, rightTreeLen);
    return res;
}