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) O(n).
- 总体时间复杂度 O ( n 2 ) O(n^2) O(n2)，这是最坏的情况。为了优化，可以使用哈希表记录中序遍历中每个元素的位置，将查找操作优化为 O ( 1 ) O(1) O(1)，从而将时间复杂度降低到 O ( n ) O(n) 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]。
- 对于左子树：
