接go语言网站开发,wordpress 转圈加载,网站建设源码包,动漫制作专业的认知题目
给定节点数为 n 的二叉树的前序遍历和中序遍历结果#xff0c;请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}#xff0c;则重建出如下图所示。 提示:
1.vin.length pre.length
2.pre 和 vin 均无重复…题目
给定节点数为 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.只需要返回根结点系统会自动输出整颗树做答案对比
数据范围0n≤2000节点的值 −10000≤val≤10000
要求空间复杂度 O(n)时间复杂度 O(n)
示例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} 解答
源代码
/** public class TreeNode {* int val 0;* TreeNode left null;* TreeNode right null;* public TreeNode(int val) {* this.val val;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param preOrder int整型一维数组 * param vinOrder int整型一维数组 * return TreeNode类*/MapInteger, Integer indexMap new HashMap();public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {// write code herefor (int i 0; i vinOrder.length; i) {indexMap.put(vinOrder[i], i);}return myBuildTree(preOrder, vinOrder, 0, vinOrder.length - 1, 0, vinOrder.length - 1);}public TreeNode myBuildTree(int[] preOrder, int[] vinOrder, int preLeft, int preRight, int vinLeft, int vinRight) {if (preLeft preRight) {return null;}TreeNode root new TreeNode(preOrder[preLeft]);// 中序遍历中根节点的索引int vinRootIndex indexMap.get(preOrder[preLeft]);// 左子树大小int leftSize vinRootIndex - vinLeft;// 右子树大小int rightSize vinRight - vinRootIndex;root.left myBuildTree(preOrder, vinOrder, preLeft 1, preLeft leftSize, vinLeft, vinRootIndex - 1);root.right myBuildTree(preOrder, vinOrder, preLeft leftSize 1, preRight, vinRootIndex 1, vinRight);return root;}
}
总结
这道题和LeetCode105一样。
详细题解见【LeetCode】105.从前序与中序遍历序列构造二叉树
