TOP101题解 | BM40#重建二叉树#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @author Senky
 * @date 2023.08.20
 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
 * @brief 通过给定前序遍历和中序遍历的结果来重建二叉树
 *  重建二叉树的基本思路是利用递归，首先从前序遍历序列中找到根节点，然后根据根节点在中序遍历序列中的位置
 *  划分出左子树和右子树的中序遍历序列
 *  接着递归构建左子树和右子树。
 * @param preOrder int整型一维数组 
 * @param preOrderLen int preOrder数组长度
 * @param vinOrder int整型一维数组 
 * @param vinOrderLen int vinOrder数组长度
 * @return TreeNode类
 */

struct TreeNode* buildTree(int* preOrder, int preStart, int preEnd, int* vinOrder, int vinStart, int vinEnd) {
    if(preStart > preEnd || vinStart > vinEnd)
    {
        return NULL;
    }
    
    // 根节点的值为前序遍历的第一个元素
    int rootVal = preOrder[preStart];
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = rootVal;
    root->left = root->right = NULL;
    
    // 在中序遍历数组中找到根节点的位置
    int rootIdx = vinStart;
    while(rootIdx <= vinEnd)
    {
        if(rootVal == vinOrder[rootIdx])
        {
            break;
        }
        rootIdx++;
    }
 
    
    // 左右子树的节点数
    int leftLen = rootIdx - vinStart;
    int rightLen = vinEnd - rootIdx;
    
    /* 递归构建左子树和右子树:
        左子树的前序和中序
        右子树的前序和中序
    */
    root->left = buildTree(preOrder, preStart + 1, preStart + leftLen,  vinOrder, vinStart,  rootIdx - 1);
    root->right = buildTree(preOrder, preStart + leftLen + 1, preEnd, vinOrder,  rootIdx + 1, vinEnd);
    
    return root;
}

struct TreeNode* reConstructBinaryTree(int* preOrder, int preOrderLen, int* vinOrder, int vinOrderLen) {
    /*每一个值都必须是合法值*/
    if(NULL == preOrder || NULL == vinOrder || preOrderLen != vinOrderLen || preOrderLen < 0)
    {
        return NULL;
    }
    
    return buildTree(preOrder, 0, preOrderLen - 1, vinOrder, 0, vinOrderLen - 1);
}