题解 | #重建二叉树#

/**
 * 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类
 */
struct TreeNode* createNode(int data) {
    struct TreeNode* Node = (struct TreeNode*)malloc(sizeof(*Node));
    Node->val = data;
    Node->left = NULL;
    Node->right = NULL;
    return Node;
}
struct TreeNode* reConstructBinaryTree(int* pre, int preLen, int* vin,
                                       int vinLen ) {
    // write code here
    if (!preLen) return NULL;
    struct TreeNode* node = createNode(pre[0]); //根结点
    int LeftLen = 0;//左子树结点个数
    while (vin[LeftLen] != pre[0]) LeftLen++; 
    int* preLeftRoot = pre + 1; //前序左子树根结点
    node->left = reConstructBinaryTree(preLeftRoot, LeftLen, vin, LeftLen);
    int* preRightRoot = pre + LeftLen + 1; //前序右子树根结点
    int* vinRightRoot = vin + LeftLen + 1;//中序右子树根结点
    int  RightLen = vinLen - LeftLen - 1; //右子树结点个数
    node->right = reConstructBinaryTree(preRightRoot, RightLen,
                                        vinRightRoot, RightLen);
    return node;

}