题解 | #重建二叉树#

/**
 * 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类
 */

int pn = 0;
struct TreeNode* dg(int* preOrder, int* vinOrder, int start, int end) {
    int i;
    struct TreeNode* tree;
    if(start > end) return NULL;
    for(i = start; i <= end; i++) {
        if(preOrder[pn] == vinOrder[i]) {
            struct TreeNode* t = (struct TreeNode*)malloc(sizeof(struct TreeNode*));
            tree = t;
            tree->val = preOrder[pn];
            pn++;
            tree->left = dg(preOrder, vinOrder, start, i - 1);
            tree->right = dg(preOrder, vinOrder, i + 1, end);
            break;
        }
    }
    return tree;
}

struct TreeNode* reConstructBinaryTree(int* preOrder, int preOrderLen, int* vinOrder, int vinOrderLen ) {
    // write code here
    if(preOrderLen == 0 || vinOrderLen == 0) return NULL;
    struct TreeNode* tree;
    tree = dg(preOrder, vinOrder, 0, vinOrderLen - 1);
    return tree;
}