秋招力扣刷题——从前序与中序遍历序列构造二叉树
一、题目要求
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
二、解法思路
- 根据二叉树的遍历结构重构二叉树，至少两种遍历方式结合，且其中一种必须是中序遍历。
- 思路：根据前序遍历找到根节点，然后从中序遍历中找到根节点的下标，拆分数组分别构造左子树和右子树。
- 代码1：此代码分割数组是左闭右开
class Solution {Map<Integer,Integer> cache=new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {for(int i=0;i<inorder.length;i++){cache.put(inorder[i],i);}return build(preorder,0,preorder.length,inorder,0,inorder.length);}private TreeNode build(int[] preorder,int prestart,int preend,int[] inorder,int instart,int inend){if(prestart>=preend||instart>=inend)return null;TreeNode root=new TreeNode(preorder[prestart]);int leftnum=cache.get(preorder[prestart])-instart;//前序加1是因为要跳过根节点root.left=build(preorder,prestart+1,prestart+leftnum+1,inorder,instart,instart+leftnum);//中序加一也是因为要跳过根节点root.right=build(preorder,prestart+leftnum+1,preend,inorder,instart+leftnum+1,inend);return root;}
}
- 代码2：次代码分割数组是左闭右闭
class Solution {Map<Integer,Integer> cache=new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {if(inorder.length==1)return new TreeNode(inorder[0]);for(int i=0;i<inorder.length;i++){cache.put(inorder[i],i);}return build(preorder,inorder,0,preorder.length-1,0,inorder.length-1);}private TreeNode build(int[] preorder,int[] inorder,int prebegin,int preend,int inbeggin,int inend){if(prebegin>preend||inbeggin>inend)return null;TreeNode root=new TreeNode(preorder[prebegin]);int index=cache.get(preorder[prebegin]);int leftnum=index-inbeggin;root.left=build(preorder,inorder,prebegin+1,prebegin+leftnum,inbeggin,inbeggin+leftnum);root.right=build(preorder,inorder,prebegin+leftnum+1,preend,inbeggin+leftnum+1,inend);return root;}
}
注：两种代码的结束条件以及分割的右区间处理方式不同，后者更容易理解一点。