北网站建设,上海app开发公司,宁波建工,服装公司网站结构105. 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder #xff0c;其中 preorder 是二叉树的先序遍历#xff0c; inorder 是同一棵树的中序遍历#xff0c;请构造二叉树并返回其根节点。 示例 1: 输入: preorder [3,9,20,15,7], inorder [9,3,15,…105. 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。 示例 1: 输入: preorder [3,9,20,15,7], inorder [9,3,15,20,7] 输出: [3,9,20,null,null,15,7] 示例 2: 输入: preorder [-1], inorder [-1] 输出: [-1] 提示: 1 preorder.length 3000 inorder.length preorder.length -3000 preorder[i], inorder[i] 3000 preorder 和 inorder 均 无重复 元素 inorder 均出现在 preorder preorder 保证 为二叉树的前序遍历序列 inorder 保证 为二叉树的中序遍历序列 题解 我们使用递归分治思想因对于所给中序和前序可通过前序序列确定第一个节点再通过此节点在中序序列中的位置进而确定左右子树各自的中序序列之后再通过其确定左右子树各自的前序序列以此可进行递归处理 同时注意某子树的中序序列长度和前序序列长度必为相等可依据此性质确定递归时inorder数组和preorder数组下标起点终点该如何选择 递归即对每个子树的中序和后序序列分别按照上述思想处理即可 代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/// 贪心法 失败
// class Solution {
// public TreeNode buildTree(int[] preorder, int[] inorder) {
// // 哈希表维护中序顺序从而判断两元素之间方向关系
// MapInteger,Integer map new HashMap();
// for(int i0;iinorder.length;i){
// map.put(inorder[i],i);
// }// // 建造节点依靠先序中序作为验证判断从而选择l或r方向延申
// // 初始化第一个位置因其为确定且唯一
// TreeNode res new TreeNode(preorder[0]);
// TreeNode temp res;// // 其余元素需要加入中序判断
// for(int i1;ipreorder.length;i){
// int level map.get(preorder[i]);
// if(level map.get(temp.val)){
// // 每次都叫node_new但是分配区域不会回收
// // 只是名字被另一片区域剥夺但因使用指针已经连接好故不会混淆
// TreeNode node_new new TreeNode(preorder[i]);
// temp.right node_new;
// temp temp.right;
// }
// else{
// // 同上 区别是若遍历到的节点在temp右方则必定temp加入此点后向right移动
// // 若在temp左方 需等待 因可能右方还有节点
// // 当然也存在右方无节点情况 此时则需要判断下一节点是否仍为temp的left
// // 若是 则temp向left移动
// if(temp.left null){
// TreeNode node_new new TreeNode(preorder[i]);
// temp.left node_new;
// }
// else{
// temp temp.left;
// // 回溯未处理情况
// i--;
// }
// }
// }// return res;
// }
// }// 递归法
class Solution {MapInteger,Integer map new HashMap(); public TreeNode buildTree(int[] preorder, int[] inorder) {// 哈希表维护中序顺序从而判断两元素之间方向关系for(int i0;iinorder.length;i){map.put(inorder[i],i);}return ToBuildTree(preorder,inorder,0,preorder.length-1,0,inorder.length-1);}public TreeNode ToBuildTree(int[] preorder,int[] inorder,int preStart,int preEnd,int inStart,int inEnd){// 中序序列和先序序列长度必为相等因此只需判断一个即可if(preStart preEnd)return null; // 对于递归设置一个终止条件即可// 根节点可立刻确定TreeNode res new TreeNode(preorder[preStart]);// 此根在中序遍历中下标位置int inorder_pre map.get(preorder[preStart]);// 运用每个子树的中序序列和其对应的前序序列长度相等的性质可推断出左子树和右子树前序序列分界点int placeLeft inorder_pre-1 - inStart;res.left ToBuildTree(preorder,inorder,preStart1,preStart1placeLeft,inStart,inorder_pre-1);int placeRight inEnd - (inorder_pre1); res.right ToBuildTree(preorder,inorder,preEnd-placeRight,preEnd,inorder_pre1,inEnd);return res;}
}结果
