每日一题-重建二叉树

题目描述

给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。

示例

输入前序遍历序列 {1,2,4,7,3,5,6,8} 和中序遍历序列 {4,7,2,1,5,3,8,6}，则重建出如下图所示。

提示：

1. vin.length == pre.length
2. pre 和 vin 均无重复元素
3. vin 出现的元素均出现在 pre 里
4. 只需要返回根结点，系统会自动输出整颗树做答案对比

数据范围：

• $n\le 2000$
• 节点的值 $-10000\le val\le 10000$

要求：

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

示例 1

输入：

[1,2,4,7,3,5,6,8], [4,7,2,1,5,3,8,6]

返回值：

{1,2,3,4,#,5,6,#,7,#,#,8}

示例 2

输入：

[1], [1]

返回值：

{1}

示例 3

输入：

[1,2,3,4,5,6,7], [3,2,4,1,6,5,7]

返回值：

{1,2,5,3,4,6,7}

代码实现

/*** struct TreeNode {*  int val;*  struct TreeNode *left;*  struct TreeNode *right;* };*//*** 在中序遍历数组中查找节点值的位置*/
int findIndex(int* inorder, int inorderStart, int inorderEnd, int val) {for (int i = inorderStart; i <= inorderEnd; i++) {if (val == inorder[i])return i;}return -1;
};/*** 通过前序遍历和中序遍历重建二叉树*/
struct TreeNode* buildTree(int* preorder, int preorderStart, int preorderEnd, int* inorder, int inorderStart, int inorderEnd) {// 如果前序遍历的范围无效，说明当前节点为空if (preorderStart > preorderEnd) {return NULL;}// 创建当前根节点struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));root->val = preorder[preorderStart];// 找到根节点在中序遍历中的位置int rootIndex = findIndex(inorder, inorderStart, inorderEnd, root->val);// 计算左子树的大小int leftTreeSize = rootIndex - inorderStart;// 构建左子树root->left = buildTree(preorder, preorderStart + 1, preorderStart + leftTreeSize, inorder, inorderStart, rootIndex - 1);// 构建右子树root->right = buildTree(preorder, preorderStart + leftTreeSize + 1, preorderEnd, inorder, rootIndex + 1, inorderEnd);return root;
};/*** 主函数，传入前序和中序遍历数组，返回根节点*/
struct TreeNode* reConstructBinaryTree(int* preOrder, int preOrderLen, int* vinOrder, int vinOrderLen ) {return buildTree(preOrder, 0, preOrderLen - 1, vinOrder, 0, vinOrderLen - 1);
}

为什么只判断前序遍历范围无效，不判断后序遍历范围有效？

1. 前序遍历和中序遍历的范围是同步的：
   在递归过程中，前序遍历和中序遍历的范围是通过递归逻辑同步调整的。具体来说：

   • 前序遍历：根节点在前序遍历的第一个位置，左子树和右子树的范围可以通过中序遍历的结果来划分。
   • 中序遍历：根节点在中序遍历中将数组分为左子树和右子树。

   当我们确定了前序遍历的范围后，中序遍历的范围也会随之确定。因此，只要前序遍历的范围有效，中序遍历的范围必然也是有效的。

2. 递归终止条件：
   递归终止条件是当某个子树为空时，即没有更多的节点可以处理。在递归逻辑中，我们通过以下方式确保递归终止：

   • 如果 preorderStart > preorderEnd，说明当前子树的前序遍历范围无效，这意味着当前子树为空。

   由于前序遍历和中序遍历的范围是同步调整的，当前序遍历范围无效时，中序遍历的范围也必然无效。