TOP101题解 | BM40#重建二叉树#
重建二叉树
https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6
/** * 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); }#TOP101#
TOP101-BM系列 文章被收录于专栏
系列的题解