机械网站建设价格,人工智能营销网站开发,江苏网站建设网站排名优化,网站 代备案#x1f451;专栏内容#xff1a;力扣刷题⛪个人主页#xff1a;子夜的星的主页#x1f495;座右铭#xff1a;前路未远#xff0c;步履不停 目录 一、题目描述1、题目2、示例 二、题目分析1、递归2、栈 一、题目描述
1、题目
剑指offer#xff1a;重建二叉树
给定节… 专栏内容力扣刷题⛪个人主页子夜的星的主页座右铭前路未远步履不停 目录 一、题目描述1、题目2、示例 二、题目分析1、递归2、栈 一、题目描述
1、题目
剑指offer重建二叉树
给定节点数为 n 的二叉树的前序遍历和中序遍历结果请重建出该二叉树并返回它的头结点。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}则重建出如下图所示。
提示: 1.vin.length pre.length 2.pre 和 vin 均无重复元素 3.vin出现的元素均出现在 pre里 4.只需要返回根结点系统会自动输出整颗树做答案对比 数据范围 n 2000 n2000 n2000节点的值 − 1000 v a l 1000 -1000val1000 −1000val1000 要求时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n ) O(n) O(n)
2、示例
示例1
输入[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]
返回值{1,2,3,4,#,5,6,#,7,#,#,8}
说明返回根节点系统会输出整颗二叉树对比结果重建结果如题面图示 示例2
输入[1],[1]
返回值{1}示例3
输入[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
返回值{1,2,5,3,4,6,7}二、题目分析
1、递归
public class Solution {public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {int n pre.length;int m vin.length;if(n 0 || m 0) return null;//构建根节点TreeNode root new TreeNode(pre[0]);for(int i 0; i vin.length; i){//找到中序遍历中的前序第一个元素if(pre[0] vin[i]){ //构建左子树root.left reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i 1), Arrays.copyOfRange(vin, 0, i)); //构建右子树root.right reConstructBinaryTree(Arrays.copyOfRange(pre, i 1, pre.length), Arrays.copyOfRange(vin, i 1, vin.length));break;}}return root;}
}
2、栈 public class Solution {public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {int n pre.length;int m vin.length;//每个遍历都不能为0if(n 0 || m 0) return null;StackTreeNode s new StackTreeNode();//首先建立前序第一个即根节点TreeNode root new TreeNode(pre[0]); TreeNode cur root;for(int i 1, j 0; i n; i){//要么旁边这个是它的左节点if(cur.val ! vin[j]){ cur.left new TreeNode(pre[i]);s.push(cur);//要么旁边这个是它的右节点或者祖先的右节点cur cur.left; }else{j;//弹出到符合的祖先while(!s.isEmpty() s.peek().val vin[j]){cur s.pop();j;}//添加右节点cur.right new TreeNode(pre[i]); cur cur.right;}}return root;}
}
