32 从前序与中序遍历序列构造二叉树

32 从前序与中序遍历序列构造二叉树

32.1 从前序与中序遍历序列构造二叉树解决方案

class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {return buildTreeHelper(preorder, inorder, 0, 0, inorder.size() - 1);}TreeNode* buildTreeHelper(vector<int>& preorder, vector<int>& inorder, int& preIdx, int inStart, int inEnd) {// 基本情况：如果遍历到空区间，返回空if (inStart > inEnd) {return nullptr;}// 当前根节点int rootVal = preorder[preIdx++];TreeNode* root = new TreeNode(rootVal);// 在中序遍历中找到根节点位置int rootIdxInInorder = find(inorder.begin() + inStart, inorder.begin() + inEnd, rootVal) - inorder.begin();// 构建左子树root->left = buildTreeHelper(preorder, inorder, preIdx, inStart, rootIdxInInorder - 1);// 构建右子树root->right = buildTreeHelper(preorder, inorder, preIdx, rootIdxInInorder + 1, inEnd);return root;}
};

思路解析：
前序遍历：首先访问根节点，然后访问左子树，再访问右子树。
中序遍历：首先访问左子树，然后访问根节点，最后访问右子树。

步骤：

• 根节点的确定：
  • 在前序遍历中，第一个元素就是树的根节点。根据这一点，我们可以直接确定根节点。
• 分割左右子树：
  • 在中序遍历中，根节点将数组分成两个部分：左子树和右子树。根节点左边的元素构成左子树，右边的元素构成右子树。
• 递归构建：
  • 根据中序遍历分割出的左右子树，递归地在前序和中序遍历中找出对应的子树，继续构建左右子树。

详细步骤

• 获取根节点：从前序遍历的第一个元素得到当前子树的根节点。
• 在中序遍历中查找根节点的位置：根节点左边的元素属于左子树，右边的元素属于右子树。
• 递归构建左右子树：递归地使用剩下的前序和中序遍历来构建左右子树。

代码解析：

• buildTree函数：主要入口函数，调用buildTreeHelper来递归构建二叉树。
• buildTreeHelper函数：递归函数，负责构建树的每个节点。
  • preIdx：指示前序遍历中当前根节点的位置。
  • inStart和inEnd：指定当前中序遍历子树的范围。
  • 每次递归通过preIdx获取根节点的值，通过在中序遍历中找到节点的位置，将数组分为左右子树，递归地构建左右子树。
• find函数：在中序遍历的子数组中找到根节点的位置，用于分割左子树和右子树。

时间复杂度：

• 由于递归遍历每个节点一次，每个节点的查找操作(在find中)在最坏的情况下是$O(n)$.
• 总体时间复杂度$O(n^2)$，这是最坏的情况。为了优化，可以使用哈希表记录中序遍历中每个元素的位置，将查找操作优化为$O(1)$，从而将时间复杂度降低到$O(n)$.

32.2 举例说明

举例说明：
假设前序遍历和中序遍历如下：

• 前序遍历：[3,9,20,15,7]

• 中序遍历：[9,3,15,20,7]

• 确定根节点

  • 前序遍历的第一个元素是3，所以根节点是3.

• 在中序遍历中找到根节点的位置

  • 根节点3在中序遍历中的位置是第2个元素，位置索引为1.
  • 这将中序遍历分为：
    • 左子树：[9]
    • 右子树：[15,20,7]

• 递归构建左子树和右子树

  • 对于左子树：
    • 在前序遍历中，根节点是9
    • 中序遍历中的9就是左子树。左子树为空，右子树也是为空。
  • 对于右子树：
    • 在前序遍历中，右子树的节点顺序是[20,15,7]
    • 在中序遍历中，右子树是[15,20,7]。