【二叉树-9】105.从前序与中序遍历序列构造二叉树

题目描述给定两个整数数组preorder和inorder其中preorder是二叉树的先序遍历inorder是同一棵树的中序遍历请构造二叉树并返回其根节点。示例 1:输入:preorder [3,9,20,15,7], inorder [9,3,15,20,7]输出:[3,9,20,null,null,15,7]示例 2:输入:preorder [-1], inorder [-1]输出:[-1]解题思路方法一递归 哈希表核心思路前序的第一个元素 当前子树的根节点在中序中找到根节点的位置左边是左子树的中序右边是右子树的中序根据左子树的长度在前序中划分出左右子树递归构造左右子树具体过程示例前序: [3, 9, 20, 15, 7] 中序: [9, 3, 15, 20, 7] 第1步: 前序第一个是 3所以根节点是 3 在中序中找到 3 的位置: 下标1 左子树中序: [9]长度1 右子树中序: [15, 20, 7]长度3 第2步: 前序中划分 左子树前序: [9]长度1 右子树前序: [20, 15, 7]长度3 第3步: 递归构造 左子树: 根9无左右 右子树: 根20左15右7 结果: 3 / \ 9 20 / \ 15 7 ✅代码实现class Solution { public: TreeNode* buildTree(vectorint preorder, vectorint inorder) { // 用哈希表记录中序中每个值的位置方便 O(1) 查找 unordered_mapint, int indexMap; for (int i 0; i inorder.size(); i) { indexMap[inorder[i]] i; } return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, indexMap); } private: TreeNode* build(vectorint preorder, int preStart, int preEnd, vectorint inorder, int inStart, int inEnd, unordered_mapint, int indexMap) { if (preStart preEnd) return nullptr; // 前序的第一个是根节点 int rootVal preorder[preStart]; TreeNode* root new TreeNode(rootVal); // 在中序中找到根节点的位置 int rootIndex indexMap[rootVal]; int leftSize rootIndex - inStart; // 左子树节点数 // 递归构造左右子树 root-left build(preorder, preStart 1, preStart leftSize, inorder, inStart, rootIndex - 1, indexMap); root-right build(preorder, preStart leftSize 1, preEnd, inorder, rootIndex 1, inEnd, indexMap); return root; } };复杂度分析维度复杂度说明时间复杂度O(n)每个节点访问一次哈希表查找 O(1)空间复杂度O(n)哈希表 O(n) 递归栈 O(h)空间复杂度说明哈希表存储 n 个值O(n)递归栈深度O(h)最坏 O(n)关键细节1. 为什么用哈希表如果不用哈希表每次找根节点在中序中的位置需要 O(n)总时间复杂度变成 O(n²)用哈希表预存位置查找变成 O(1)2. 如何划分左右子树的前序和中序范围前序: [根, 左子树前序, 右子树前序] 中序: [左子树中序, 根, 右子树中序] 左子树: 前序范围: [preStart1, preStartleftSize] 中序范围: [inStart, rootIndex-1] 右子树: 前序范围: [preStartleftSize1, preEnd] 中序范围: [rootIndex1, inEnd]关键leftSize rootIndex - inStart3. 递归终止条件if (preStart preEnd) return nullptr;当范围为空时返回nullptr。4. 为什么不用preStart preEnd用更通用可以处理空范围用只能处理单个节点容易出错方法二不用哈希表O(n²)代码实现class Solution { public: TreeNode* buildTree(vectorint preorder, vectorint inorder) { return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1); } private: TreeNode* build(vectorint preorder, int preStart, int preEnd, vectorint inorder, int inStart, int inEnd) { if (preStart preEnd) return nullptr; int rootVal preorder[preStart]; TreeNode* root new TreeNode(rootVal); // 在中序中线性查找根节点 int rootIndex inStart; while (inorder[rootIndex] ! rootVal) rootIndex; int leftSize rootIndex - inStart; root-left build(preorder, preStart 1, preStart leftSize, inorder, inStart, rootIndex - 1); root-right build(preorder, preStart leftSize 1, preEnd, inorder, rootIndex 1, inEnd); return root; } };复杂度时间 O(n²)空间 O(h)两种方法对比方法时间复杂度空间复杂度推荐度递归 哈希表O(n)O(n)⭐⭐⭐⭐⭐递归线性查找O(n²)O(h)⭐⭐⭐总结要点说明核心思想前序找根中序分左右递归构造关键操作哈希表存中序位置O(1) 查找时间复杂度O(n)空间复杂度O(n)