设计师怎么弄个人网站济南seo网站关键词排名

设计师怎么弄个人网站,济南seo网站关键词排名,深圳电器公司,网红营销是什么从前序与中序遍历序列构造二叉树#xff08;LeetCode 105#xff09; 题目链接#xff1a;从前序与中序遍历序列构造二叉树#xff08;LeetCode 105#xff09; 难度#xff1a;中等 1. 题目描述 给定两个整数数组 preorder 和 inorder #xff0c;其中 preorder 是二叉…从前序与中序遍历序列构造二叉树LeetCode 105题目链接从前序与中序遍历序列构造二叉树LeetCode 105难度中等1. 题目描述给定两个整数数组preorder和inorder其中preorder是二叉树的先序遍历inorder是同一棵树的中序遍历请构造二叉树并返回其根节点。要求树中不存在重复元素数组长度 1 n 3000-3000 preorder[i], inorder[i] 3000示例输入: preorder [3,9,20,15,7], inorder [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]输入: preorder [-1], inorder [-1] 输出: [-1]2. 问题分析2.1 规律先序遍历根节点 - 左子树 - 右子树中序遍历左子树 - 根节点 - 右子树先序的第一个元素总是根节点在中序中找到根节点的位置可以分割左/右子树。递归构建左子树的前序/中序子序列右子树的前序/中序子序列。核心问题如何高效找到中序中根节点的位置以分割子树2.2 贪心思路我们使用递归 哈希表优化使用哈希表存储中序遍历的值到索引的映射便于 O(1) 查找根节点位置。递归函数参数为前序/中序的起始/结束索引。步骤如果子树为空start end返回 None。取前序第一个元素作为根pre_idx 1。在中序中找到根索引 root_in_idx。递归构建左子树中序 [in_start, root_in_idx-1]前序相应部分。递归构建右子树中序 [root_in_idx1, in_end]前序相应部分。全局 pre_idx 跟踪前序位置避免切片开销。3. 代码实现Python# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution:defbuildTree(self,preorder:List[int],inorder:List[int])-Optional[TreeNode]:defhelper(in_start,in_end):nonlocalpre_idxifin_startin_end:returnNoneroot_valpreorder[pre_idx]rootTreeNode(root_val)pre_idx1root_in_idxidx_map[root_val]root.lefthelper(in_start,root_in_idx-1)root.righthelper(root_in_idx1,in_end)returnroot nlen(preorder)idx_map{val:ifori,valinenumerate(inorder)}pre_idx0returnhelper(0,n-1)C/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */classSolution{public:TreeNode*buildTree(vectorintpreorder,vectorintinorder){unordered_mapint,intidx_map;for(inti0;iinorder.size();i){idx_map[inorder[i]]i;}intpre_idx0;returnhelper(preorder,inorder,idx_map,pre_idx,0,inorder.size()-1);}private:TreeNode*helper(vectorintpreorder,vectorintinorder,unordered_mapint,intidx_map,intpre_idx,intin_start,intin_end){if(in_startin_end){returnnullptr;}introot_valpreorder[pre_idx];TreeNode*rootnewTreeNode(root_val);pre_idx;introot_in_idxidx_map[root_val];root-lefthelper(preorder,inorder,idx_map,pre_idx,in_start,root_in_idx-1);root-righthelper(preorder,inorder,idx_map,pre_idx,root_in_idx1,in_end);returnroot;}};4. 复杂度分析时间复杂度O(n)哈希表构建 O(n)递归遍历每个节点一次空间复杂度O(n)哈希表 O(n)递归栈最坏 O(n)5. 总结树重建问题遍历序列→ 递归分割是首选核心使用哈希表优化索引查找很通用类似 BFS 的序列化但这里是反序列化可扩展到后序 中序的变体复习面试经典150题[012]O(1) 时间插入、删除和获取随机元素LeetCode 380面试经典150题[042]有效的字母异位词LeetCode 242面试经典150题[057]链表中是否有环LeetCode 141