题解 | 重建二叉树
重建二叉树
https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=295&tqId=23282&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
private:
unordered_map<int, int> vinIndex; // 中序遍历值到索引的映射
TreeNode* build(vector<int>& preOrder, int preStart, int preEnd,
vector<int>& vinOrder, int vinStart, int vinEnd) {
if (preStart > preEnd || vinStart > vinEnd) {
return nullptr;
}
// 前序遍历第一个节点是根节点
int rootVal = preOrder[preStart];
TreeNode* root = new TreeNode(rootVal);
// 在中序遍历中找到根节点位置
int rootIndex = vinIndex[rootVal];
int leftSize = rootIndex - vinStart; // 左子树节点个数
// 递归构建左右子树
root->left = build(preOrder, preStart + 1, preStart + leftSize,
vinOrder, vinStart, rootIndex - 1);
root->right = build(preOrder, preStart + leftSize + 1, preEnd,
vinOrder, rootIndex + 1, vinEnd);
return root;
}
public:
TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
if (preOrder.empty() || vinOrder.empty() ||
preOrder.size() != vinOrder.size()) {
return nullptr;
}
// 构建中序遍历的索引映射
for (int i = 0; i < vinOrder.size(); i++) {
vinIndex[vinOrder[i]] = i;
}
return build(preOrder, 0, preOrder.size() - 1,
vinOrder, 0, vinOrder.size() - 1);
}
};
算法核心 前序遍历确定根节点：前序遍历的第一个元素就是当前子树的根节点 中序遍历划分左右子树：在中序遍历中找到根节点，左边是左子树，右边是右子树 递归构建：分别对左右子树递归执行上述过程 关键参数说明 preStart, preEnd：当前子树在前序遍历中的范围 vinStart, vinEnd：当前子树在中序遍历中的范围 leftSize：左子树的节点个数，用于确定子树范围 vinIndex：哈希表，存储中序遍历值到索引的映射，加速查找 时间复杂度分析 时间复杂度：O(n) 每个节点只处理一次 哈希表查找根节点位置为 O(1) 空间复杂度：O(n) 递归栈深度为树的高度 哈希表存储 n 个元素的映射
DS之二叉树 文章被收录于专栏
二叉树的遍历:前,中,后,层次 二叉树的存储结构:链式,顺序(主要用于完全二叉树) 二叉树的应用场景:二叉搜索树（BST）,平衡二叉搜索树（AVL树、红黑树）,堆,哈夫曼树,表达式树
