企业官网建设流程全解析

网站建设制作找哪家,怎么查看网站开发使用什么技术,大型网站建设建设公司排名,企业门户网站属于什么层【Leetcode105106】用遍历序列还原二叉树#xff1a;前序中序、后序中序的统一套路与“先建哪边”的坑二叉树的遍历序列题#xff0c;特别像“看上去是模板题#xff0c;但真正拉开差距的是细节”。很多时候不是不会写#xff0c;而是写着写着就把“顺序”弄反#x…【Leetcode105106】用遍历序列还原二叉树前序中序、后序中序的统一套路与“先建哪边”的坑二叉树的遍历序列题特别像“看上去是模板题但真正拉开差距的是细节”。很多时候不是不会写而是写着写着就把“顺序”弄反结果要么构出来的树不对要么直接递归爆栈。做这类题我习惯先把两件事牢牢记住前序 / 后序序列负责告诉我根节点是谁中序序列负责告诉我左子树和右子树的边界在哪里接下来就交给递归每次在中序区间里切一刀把大问题切成左右子树的小问题继续做。这篇文章把两道题放在一起讲题目 A前序 preorder 中序 inorder 构造树题目 B中序 inorder 后序 postorder 构造树并且会重点解释一个非常高频的问题也是最容易踩坑的地方为什么在“后序中序”构造树里递归必须先构建 right 再构建 left如果把 left 放前面为什么会直接 StackOverflow一、 Leetcode105preorder inorder 构造二叉树题目回顾给两个数组preorder先序遍历根 → 左 → 右inorder中序遍历左 → 根 → 右要求构造原二叉树并返回根节点。示例preorder [3,9,20,15,7]inorder [9,3,15,20,7]输出树层序[3,9,20,null,null,15,7]先序 中序的关键结论这里的思路非常“干脆”先序的第一个元素一定是当前子树的根在中序里找到这个根的位置就能把中序分成左半段左子树右半段右子树二、来看这段代码题目 Leetcode105 的实现classSolution{publicintpreindex0;publicTreeNodebuildTree(int[]preorder,int[]inorder){returnbuildChildTree(preorder,inorder,0,inorder.length-1);}publicTreeNodebuildChildTree(int[]preorder,int[]inorder,intibegin,intiend){if(ibeginiend)returnnull;TreeNoderootnewTreeNode(preorder[preindex]);introotIndexfindval(inorder,ibegin,iend,preorder[preindex]);preindex;root.leftbuildChildTree(preorder,inorder,ibegin,rootIndex-1);root.rightbuildChildTree(preorder,inorder,rootIndex1,iend);returnroot;}privateintfindval(int[]inorder,intibegin,intiend,intval){for(intiibegin;iiend;i){if(inorder[i]val)returni;}return-1;}}这段代码的整体思路拆成三句话把它当成一个“递归工厂”每次负责生产一棵子树preindex永远指向“当前子树的根”因为先序是“根左右”在inorder[ibegin..iend]中找到根的位置rootIndex递归构建左区间和右区间最后把它们挂到 root 上为什么这里是“先构建 left再构建 right”原因很本质先序遍历的顺序就是根 → 左 → 右根节点用掉之后preindex指向的下一个节点就是左子树的根。如果这时候先去建右子树那就相当于拿着左子树的根去右区间里找必然错位。所以题目 A 的顺序必须是root.left...root.right...三、题目 Binorder postorder 构造二叉树题目回顾给两个数组inorder中序遍历左 → 根 → 右postorder后序遍历左 → 右 → 根要求构造原二叉树并返回根节点。示例inorder [9,3,15,20,7]postorder [9,15,7,20,3]输出树层序[3,9,20,null,null,15,7]后序 中序的关键结论这里同样抓住“根”和“切割”两件事后序的最后一个元素一定是当前子树的根中序切分方式仍然一样左边是左子树右边是右子树但这里有一个超级关键点如果从后往前消费 postorder顺序是“根 → 右 → 左”为什么会这样因为后序是左 → 右 → 根倒过来读就是根 → 右 → 左这个“倒序的顺序”就是题目 B 的坑点核心。四、来看这段代码Leetcode106 的实现classSolution{publicintpreindex0;publicTreeNodebuildTree(int[]inorder,int[]postorder){preindexpostorder.length-1;returnbuildChildTree(postorder,inorder,0,inorder.length-1);}publicTreeNodebuildChildTree(int[]postorder,int[]inorder,intibegin,intiend){if(ibeginiend)returnnull;TreeNoderootnewTreeNode(postorder[preindex]);introotIndexfindval(inorder,ibegin,iend,postorder[preindex]);if(preindex0)preindex--;root.rightbuildChildTree(postorder,inorder,rootIndex1,iend);root.leftbuildChildTree(postorder,inorder,ibegin,rootIndex-1);returnroot;}privateintfindval(int[]inorder,intibegin,intiend,intval){for(intiibegin;iiend;i){if(inorder[i]val)returni;}return-1;}}这段代码的整体思路仍然是同一套路如果只看骨架会发现它和题目 A 非常像preindex从 postorder 的最后开始走每次取当前根在 inorder 切出左右子树区间递归构建左右子树并挂上去真正的差别只有一个点但这个点能决定生死题目 Apreindex从左往右走根之后是左子树题目 Bpreindex从右往左走根之后是右子树于是就引出了那个关键疑问。五、关键疑问为什么题目 Leetcode106 不能先构建 left问题说得再具体一点如果把这两行交换顺序root.left ...放到root.right ...前面就会 StackOverflow换回来又好了。为什么答案一句话就够因为倒序 postorder 的消费顺序是“根 → 右 → 左”如果先构建 left就会拿“右子树的根”去左区间里找找不到导致 rootIndex -1区间无法正确缩小递归不收敛最终爆栈。下面把这个“爆栈链条”详细展开这部分是理解的关键。六、爆栈是怎么发生的错位消费 找不到根 区间不收缩用示例来走一次inorder[9, 3, 15, 20, 7]postorder[9, 15, 7, 20, 3]初始化preindex 4指向3。1第一步取根 3 没问题root 3在 inorder 找到 3 的位置rootIndex 1切分左区间[0..0]→[9]右区间[2..4]→[15,20,7]preindex-- 指向 20注意下一位是 202如果先构建 left就直接错位此时preindex指向的是20但左区间里只有9。如果先递归构建 left会做root postorder[preindex] 20然后在 inorder 的左区间[9]里找 20找不到 →findval返回-13rootIndex -1 会引发致命后果接下来递归会用rootIndex去计算左右区间右区间rootIndex 1 .. iend→0 .. iend左区间ibegin .. rootIndex - 1→ibegin .. -2左区间很快会因为ibegin iend返回 null这还好。但右区间变成了0..iend——很可能比当前区间还大或几乎没变递归规模不缩小。递归能结束依赖的就是这句 base caseif(ibeginiend)returnnull;可一旦区间不缩小base case 永远触发不了就会不断递归下去最终 StackOverflow。4为什么换成先 right 就好了因为preindex--后指向的 20恰好是右子树的根右区间也确实包含 20所以rootIndex 能正确找到inorder 区间会不断缩小递归自然收敛整个过程稳定结束所以题目 B 必须root.right...root.left...这不是“写法偏好”是由“倒序消费 postorder 的顺序 根右左”决定的。七、把两题统一成一个“记忆模型”如果不想每次都重推可以只记一个模型非常好用中序 inorder负责切割左右边界另一种遍历前序/后序负责 warn 我根节点出现的位置消费遍历数组的方向决定先建哪一边对应关系前序 中序前序根 左 右从左往右消费根之后是左子树所以先建 left再建 right后序 中序后序左 右 根从右往左消费根之后是右子树倒序根右左所以先建 right再建 left这就是顺序的“根本原因”。八、一个很实用的工程化补充O(n²) 可以优化到 O(n)两段代码都用findval在 inorder 区间线性扫描找 rootIndex。最坏情况下树极度不平衡会退化成 O(n²)。更稳的做法是先用 HashMap 把 inorder 的值映射到下标value - index每次找 rootIndex 直接 O(1)n 最大 3000其实不少平台 O(n²) 也能过但写成 O(n) 更像“标准答案”。九、小结这两题的本质是一件事先序/后序给出“根”中序定位根的位置切成左右子树区间递归重复关键差异只有一个消费遍历序列的方向不同导致必须先构建的子树不同前序从左到右根之后是左 ⇒先 left 后 right后序从右到左根之后是右 ⇒先 right 后 left在后序题里如果先建 left会把右子树根塞进左区间根下标找不到导致区间不收缩最后爆栈这一套想明白之后类似的题如“前序中序还原”“后序中序还原”“层序中序是否可行”等都会变得非常直观先问“根从哪来”再问“中序怎么切”最后问“谁先被消费”。