题解 | #重建二叉树#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pre int整型一维数组 
 * @param preLen int pre数组长度
 * @param vin int整型一维数组 
 * @param vinLen int vin数组长度
 * @return TreeNode类
 */
struct TreeNode* reConstructBinaryTree(int* pre, int preLen, int* vin, int vinLen ) {
    if(preLen==0){
       return NULL;
    }
    //初始化一个结点
    struct TreeNode* head=(struct TreeNode*)malloc(sizeof(struct TreeNode));
    //传入的先序遍历顺序第一个即为当前树的根节点
    head->val=*pre;
    //在中序遍历中寻找当前根节点所在位置
    int k=0;
    int length_left=0;
    int length_right=0;
    while(pre[0]!=vin[k]){
        k++;
    }
    //左子树长度即为k
    length_left=k;
    //右子树长度
    length_right=vinLen-k-1;
    //递归处理左子树和右子树
    head->left=reConstructBinaryTree(pre+1,length_left,vin,length_left);
    head->right=reConstructBinaryTree(pre+1+k,length_right,vin+k+1,length_right);
    
    return head;
}