企业官网建设流程全解析

小企业网站建设多少钱,网站页面文案,腾讯邮箱网页登录入口,如何再国外网站做折扣根据前序和后序遍历构造二叉树 问题描述 给定前序遍历和后序遍历的结果#xff0c;构造并返回二叉树。 注意#xff1a;理论上#xff0c;仅凭前序和后序遍历无法唯一确定一棵二叉树#xff08;缺少中序遍历的根位置信息#xff09;。保证#xff1a; 所有节点值唯一返回…根据前序和后序遍历构造二叉树问题描述给定前序遍历和后序遍历的结果构造并返回二叉树。注意理论上仅凭前序和后序遍历无法唯一确定一棵二叉树缺少中序遍历的根位置信息。保证所有节点值唯一返回任意一个满足条件的二叉树即可遍历定义前序遍历根 → 左子树 → 右子树后序遍历左子树 → 右子树 → 根示例输入:preorder[1,2,4,5,3,6,7],postorder[4,5,2,6,7,3,1]输出:[1,2,3,4,5,6,7]解释:1/\23/\/\4567输入:preorder[1,2,3],postorder[3,2,1]输出:[1,2,null,null,3]或[1,null,2,3,null]算法思路核心前序遍历的第一个元素 根节点后序遍历的最后一个元素 根节点前序遍历的第二个元素 左子树的根如果有左子树在后序遍历中找到左子树根的位置可以确定左子树的范围代码实现方法一递归 哈希表importjava.util.*;// 二叉树节点定义classTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(){}TreeNode(intval){this.valval;}TreeNode(intval,TreeNodeleft,TreeNoderight){this.valval;this.leftleft;this.rightright;}}classSolution{/** * 根据前序和后序遍历构造二叉树 * * param preorder 前序遍历数组 * param postorder 后序遍历数组 * return 构造的二叉树根节点 * * 算法思路 * 1. 使用哈希表存储后序遍历中每个值的索引 * 2. 递归分治根据左子树根确定左右子树范围 * 3. 默认将不确定的子树作为左子树 */publicTreeNodeconstructFromPrePost(int[]preorder,int[]postorder){// 创建哈希表值 - 后序遍历中的索引MapInteger,IntegerpostIndexMapnewHashMap();for(inti0;ipostorder.length;i){postIndexMap.put(postorder[i],i);}returnbuildTree(preorder,0,preorder.length-1,postorder,0,postorder.length-1,postIndexMap);}/** * 递归构建二叉树 * * param preorder 前序遍历数组 * param preStart 前序起始索引 * param preEnd 前序结束索引 * param postorder 后序遍历数组 * param postStart 后序起始索引 * param postEnd 后序结束索引 * param postIndexMap 后序值到索引的映射 * return 子树根节点 */privateTreeNodebuildTree(int[]preorder,intpreStart,intpreEnd,int[]postorder,intpostStart,intpostEnd,MapInteger,IntegerpostIndexMap){// 基础情况空范围if(preStartpreEnd){returnnull;}// 创建根节点TreeNoderootnewTreeNode(preorder[preStart]);// 基础情况只有一个节点if(preStartpreEnd){returnroot;}// 找到左子树的根节点前序的第二个元素intleftRootValpreorder[preStart1];intleftRootPostIndexpostIndexMap.get(leftRootVal);// 计算左子树的节点数量intleftSubtreeSizeleftRootPostIndex-postStart1;// 递归构建左子树// 左子树前序范围[preStart1, preStartleftSubtreeSize]// 左子树后序范围[postStart, leftRootPostIndex]root.leftbuildTree(preorder,preStart1,preStartleftSubtreeSize,postorder,postStart,leftRootPostIndex,postIndexMap);// 递归构建右子树// 右子树前序范围[preStartleftSubtreeSize1, preEnd]// 右子树后序范围[leftRootPostIndex1, postEnd-1]root.rightbuildTree(preorder,preStartleftSubtreeSize1,preEnd,postorder,leftRootPostIndex1,postEnd-1,postIndexMap);returnroot;}}方法二简洁递归classSolution{/** * 简洁不使用额外参数 */publicTreeNodeconstructFromPrePost(int[]preorder,int[]postorder){if(preorder.length0)returnnull;TreeNoderootnewTreeNode(preorder[0]);if(preorder.length1)returnroot;// 找到左子树根在后序中的位置intleftRootIndex0;for(inti0;ipostorder.length;i){if(postorder[i]preorder[1]){leftRootIndexi;break;}}// 分割数组intleftSizeleftRootIndex1;int[]preLeftArrays.copyOfRange(preorder,1,1leftSize);int[]preRightArrays.copyOfRange(preorder,1leftSize,preorder.length);int[]postLeftArrays.copyOfRange(postorder,0,leftSize);int[]postRightArrays.copyOfRange(postorder,leftSize,postorder.length-1);// 递归构建root.leftconstructFromPrePost(preLeft,postLeft);root.rightconstructFromPrePost(preRight,postRight);returnroot;}}算法分析时间复杂度O(n)每个节点被访问一次哈希表查找为 O(1)总体线性时间空间复杂度O(n)哈希表O(n)递归栈O(h)其中 h 是树的高度最坏情况链状树O(n)算法过程1preorder [1,2,4,5,3,6,7], postorder [4,5,2,6,7,3,1]递归过程第一层 - root 1 - leftRoot 2, 在postorder中索引 2 - leftSize 2 - 0 1 3 - 左子树: pre[2,4,5], post[4,5,2] - 右子树: pre[3,6,7], post[6,7,3] 第二层左子树 - root 2 - leftRoot 4, 在post中索引 0 - leftSize 0 - 0 1 1 - 左子树: pre[4], post[4] - 右子树: pre[5], post[5] 第二层右子树 - root 3 - leftRoot 6, 在post中索引 0 - leftSize 0 - 0 1 1 - 左子树: pre[6], post[6] - 右子树: pre[7], post[7] 叶子节点直接返回2preorder [1,2,3], postorder [3,2,1]递归过程第一层 - root 1 - leftRoot 2, 在postorder中索引 1 - leftSize 1 - 0 1 2 - 左子树: pre[2,3], post[3,2] - 右子树: pre[], post[] → null 第二层左子树 - root 2 - leftRoot 3, 在post中索引 0 - leftSize 0 - 0 1 1 - 左子树: pre[3], post[3] - 右子树: null 结果1为根2为左子3为2的左子 1 / 2 / 3测试用例importjava.util.*;publicclassTest{// 前序遍历publicstaticListIntegerpreorderTraversal(TreeNoderoot){ListIntegerresultnewArrayList();preorderHelper(root,result);returnresult;}privatestaticvoidpreorderHelper(TreeNodenode,ListIntegerresult){if(nodenull)return;result.add(node.val);preorderHelper(node.left,result);preorderHelper(node.right,result);}// 后序遍历publicstaticListIntegerpostorderTraversal(TreeNoderoot){ListIntegerresultnewArrayList();postorderHelper(root,result);returnresult;}privatestaticvoidpostorderHelper(TreeNodenode,ListIntegerresult){if(nodenull)return;postorderHelper(node.left,result);postorderHelper(node.right,result);result.add(node.val);}publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 测试用例1完整二叉树int[]pre1{1,2,4,5,3,6,7};int[]post1{4,5,2,6,7,3,1};TreeNoderoot1solution.constructFromPrePost(pre1,post1);System.out.println(Test 1 Preorder: preorderTraversal(root1));// [1,2,4,5,3,6,7]System.out.println(Test 1 Postorder: postorderTraversal(root1));// [4,5,2,6,7,3,1]// 测试用例2只有左子树int[]pre2{1,2,3};int[]post2{3,2,1};TreeNoderoot2solution.constructFromPrePost(pre2,post2);System.out.println(Test 2 Preorder: preorderTraversal(root2));// [1,2,3]System.out.println(Test 2 Postorder: postorderTraversal(root2));// [3,2,1]// 测试用例3只有右子树int[]pre3{1,2,3};int[]post3{2,3,1};TreeNoderoot3solution.constructFromPrePost(pre3,post3);System.out.println(Test 3 Preorder: preorderTraversal(root3));// [1,2,3]System.out.println(Test 3 Postorder: postorderTraversal(root3));// [2,3,1]// 测试用例4单个节点int[]pre4{1};int[]post4{1};TreeNoderoot4solution.constructFromPrePost(pre4,post4);System.out.println(Test 4 Preorder: preorderTraversal(root4));// [1]System.out.println(Test 4 Postorder: postorderTraversal(root4));// [1]// 测试用例5两个节点int[]pre5{1,2};int[]post5{2,1};TreeNoderoot5solution.constructFromPrePost(pre5,post5);System.out.println(Test 5 Preorder: preorderTraversal(root5));// [1,2]System.out.println(Test 5 Postorder: postorderTraversal(root5));// [2,1]// 测试用例6复杂树int[]pre6{1,2,4,5,3,6};int[]post6{4,5,2,6,3,1};TreeNoderoot6solution.constructFromPrePost(pre6,post6);System.out.println(Test 6 Preorder: preorderTraversal(root6));// [1,2,4,5,3,6]System.out.println(Test 6 Postorder: postorderTraversal(root6));// [4,5,2,6,3,1]// 测试用例7大数值int[]pre7{100,200,300};int[]post7{300,200,100};TreeNoderoot7solution.constructFromPrePost(pre7,post7);System.out.println(Test 7 Preorder: preorderTraversal(root7));// [100,200,300]System.out.println(Test 7 Postorder: postorderTraversal(root7));// [300,200,100]}}关键点索引计算左子树大小 leftRootPostIndex - postStart 1右子树后序范围不包含最后一个元素根节点边界条件空数组返回 null单元素数组直接返回节点哈希表避免每次线性搜索后序数组将时间复杂度从 O(n²) 优化到 O(n)常见问题为什么不能唯一确定二叉树例如只有左子树 或 只有右子树在前序和后序中表现相同前序[1,2]后序[2,1] 可以是 1-left2 或 1-right2如果需要唯一需要中序遍历作为额外信息前序中序 或 中序后序 可以唯一确定二叉树