题解 | #二叉树中和为某一值的路径(二)#

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/*
* pre: 前序数组
* lp：pre及其子数组的左起始下标
* rp: pre及其子数组的右结尾下标
* vin :中序数组
* li: vin及其子数组的左起始下标
* ri: vin及其子数组的右结尾下标
*/
static struct TreeNode* rebuild_tree(int *pre, int lp, int rp, int *vin, int li, int ri)
{
    if (lp > rp || li > ri) {
        return NULL;
    }
    struct TreeNode *root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = pre[lp];
    int in_offset = 0;  /* 表示前序数组中的根节点值在中序数组的位置偏移,等于前序数组的左子树的节点个数 */
    for (int i = li; i <= ri; i++) {
        if (pre[lp] == vin[i]) {
            break;
        }
        in_offset++;
    }
    root->left = rebuild_tree(pre, lp + 1, lp + in_offset, vin, li, li + in_offset - 1);
    root->right = rebuild_tree(pre, lp + in_offset + 1, rp, vin, li + in_offset + 1, ri);
    return root;
}
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @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 ) {
    // write code here
    if (pre == NULL || vin == NULL || preLen <= 0 || vinLen <=0) {
        return NULL;
    }
    return rebuild_tree(pre, 0, preLen - 1, vin, 0, vinLen -1);
}