[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]
{1,2,3,4,#,5,6,#,7,#,#,8}返回根节点，系统会输出整颗二叉树对比结果，重建结果如题面图示
[1],[1]
{1}[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
{1,2,5,3,4,6,7}
//利用中序遍历，根节点在中间的特性，递归解决
public class Solution {
/**
* 给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
*
*
* @param preOrder int整型一维数组
* @param vinOrder int整型一维数组
* @return TreeNode类
*/
public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {
return findRoot(preOrder, vinOrder);
}
//获取子树根节点
public TreeNode findRoot(int[] preOrder, int[] vinOrder) {
if (preOrder.length == 0 || vinOrder.length == 0) {
return null;
}
int rootVal = preOrder[0];
TreeNode root = new TreeNode(rootVal);
int index = findIndex(rootVal, vinOrder); //获取根节点的位置
//Arrays.copyOfRange左闭右开，右标允许越界
root.left = findRoot(Arrays.copyOfRange(preOrder, 1, index + 1),
Arrays.copyOfRange(vinOrder, 0, index));
root.right = findRoot(Arrays.copyOfRange(preOrder, index + 1, preOrder.length),
Arrays.copyOfRange(vinOrder, index + 1, vinOrder.length));
return root;
}
//获取目标在数组中的下标
public int findIndex(int target, int[] array) {
for (int i = 0; i < array.length; i++) {
if (array[i] == target) {
return i;
}
}
return -1;
}
} 
import java.util.*;
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre, int [] vin) {
return dfs(0, 0, vin.length - 1, pre, vin);
}
public TreeNode dfs(int preStart, int vinStart, int vinEnd,
int[] preOrder,int[] vinOrder) {
//元素为空//位置不对
if (preStart > preOrder.length - 1 || vinStart > vinEnd) {
return null;
}
//从先序遍历首元素构建结点
TreeNode root = new TreeNode(preOrder[preStart]);
int index = 0;
//查找中序遍历结果位置
for (int i = vinStart; i <= vinEnd; i++ ) {
if (vinOrder[i] == root.val) {
index = i;
break;
}
}
//左结点为先序下一个结点,且该节点位于index左侧
root.left = dfs(preStart + 1, vinStart, index - 1, preOrder, vinOrder);
//右结点先序位置为当前结点先序位置+(当前结点左子树数量(当前中序位置-中序开始位置)+当前结点)
root.right = dfs(preStart + index - vinStart + 1, index + 1, vinEnd, preOrder,vinOrder);
return root;
}
} 
public class Solution {
Map<Integer,Integer> map=new HashMap<>();
public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
for(int i=0;i<vin.length;i++){
map.put(vin[i],i);
}
return build(pre,0,pre.length,vin,0,vin.length);
}
public TreeNode build(int[] pre,int preStart,int preEnd,int[] vin,int vinStart,int vinEnd){
if(preStart>=preEnd||vinStart>=vinEnd){
return null;
}
int rootIndex=map.get(pre[preStart]);
TreeNode root=new TreeNode(vin[rootIndex]);
int leftValue=rootIndex-vinStart;
//处理左右
//pre 头左右 //vin 左头右
root.left=build(pre,preStart+1,preStart+1+leftValue,vin,vinStart,rootIndex);
root.right=build(pre,preStart+1+leftValue,preEnd,vin,rootIndex+1,vinEnd);
return root;
}
} 
public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
if (pre == null || vin == null || pre.length == 0 || vin.length == 0) return null;
//取得根节点
TreeNode root = new TreeNode(pre[0]);
int vinRootIndex = 0;
for (int i = 0; i < vin.length; i++) {
if (vin[i] == root.val) {
vinRootIndex = i;
break;
}
}
//左子树中序
int[] leftVin = null;
int[] leftPre = null;
if (vinRootIndex != 0) {
leftVin = Arrays.copyOfRange(vin, 0, vinRootIndex);
leftPre = Arrays.copyOfRange(pre, 1, leftVin.length + 1);
}
//右子树中序
int[] rightVin = null;
if ( vinRootIndex + 1 <= vin.length - 1 ) {
rightVin = Arrays.copyOfRange(vin, vinRootIndex + 1, vin.length );
}
//左子树的前序
//右子树前序
int[] rightPre = null;
int temp = 0;
if (leftVin != null) {
temp = leftVin.length;
}
if (temp + 1 <= pre.length - 1) {
rightPre = Arrays.copyOfRange(pre, temp + 1, pre.length);
}
root.left = reConstructBinaryTree(leftPre, leftVin);
root.right = reConstructBinaryTree(rightPre, rightVin);
return root;
}
} 
public class Solution {
// root index = 1
// 先序遍历：[1,2,4,7,3,5,6,8]
// 中序遍历：[4,7,2,1,5,3,8,6]
// 具体思路是：先通过先序遍历的特点找到跟节点，然后通过跟节点来找到根节点在
// 中序遍历中的位置，然后根据中序遍历的特点(左根右)，root左边的就是左子树的个数
// root右边的就是右子树的个数，根据这个特点来通过本方法找到root.left，root.right
// 再通过递归，找到每一个节点。
public TreeNode reConstructBinaryTree(int [] pre, int [] vin) {
if (pre == null || pre.length == 0) return null;
// 构建具体的树根
TreeNode root = new TreeNode(pre[0]);
// 通过先序遍历和中序遍历来找到根节点在中序遍历的位置
int index = findRootIndexInOrder(pre, vin);
// 通过递归构建左子树
root.left = reConstructBinaryTree(
Arrays.copyOfRange(pre, 1, index + 1),
Arrays.copyOfRange(vin, 0, index)
);
// 通过递归构建右子树
root.right = reConstructBinaryTree(
Arrays.copyOfRange(pre, index + 1, pre.length),
Arrays.copyOfRange(vin, index + 1, vin.length)
);
return root;
}
public int findRootIndexInOrder(int[] pre, int[] vin) {
for (int i = 0; i < vin.length; i++) {
if (pre[0] == vin[i]) return i;
}
return 0;
}
} 
// 12/13组用例通过，最后一个用例没通过
import java.util.*;
import java.util.stream.Collectors;
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre, int [] vin) {
List<Integer> leftVinList = new ArrayList<>();
List<Integer> rightVinList = new ArrayList<>();
List<Integer> preList = Arrays.stream(pre).boxed().collect(Collectors.toList());
List<Integer> vinList = Arrays.stream(vin).boxed().collect(Collectors.toList());
if (preList.size() == 0 || vinList.size() == 0) return null;
for (int i = 0; i < vinList.size(); i++) {
if (vinList.get(i) == pre[0]) {
leftVinList = vinList.subList(0, i);
rightVinList = vinList.subList(i + 1, vinList.size());
}
}
TreeNode rootNode = new TreeNode(preList.get(0));
buildTree(rootNode, preList, leftVinList, rightVinList);
return rootNode;
}
private void buildTree(TreeNode rootNode, List<Integer> preList,
List<Integer> leftVinList, List<Integer> rightVinList) {
if (leftVinList != null && leftVinList.size() > 0) {
int val = 0;
for (Integer it : preList) {
// 第一次出现的是左子树节点
if (leftVinList.contains(it)) {
val = it;
break;
}
}
TreeNode leftNode = new TreeNode(val);
rootNode.left = leftNode;
ArrayList<Integer> sonTreePreList = new ArrayList<>();
for (Integer it : preList) {
if (leftVinList.contains(it)) {
sonTreePreList.add(it);
}
}
List<Integer> sonTreeLeftVinList = new ArrayList<>();
List<Integer> sonTreeRightVinList = new ArrayList<>();
for (int i = 0; i < leftVinList.size(); i++) {
if (leftVinList.get(i) == sonTreePreList.get(0)) {
sonTreeLeftVinList = leftVinList.subList(0, i);
sonTreeRightVinList = leftVinList.subList(i + 1, leftVinList.size());
}
}
// 递归构建左子树
if (sonTreePreList != null && sonTreePreList.size() > 0) {
buildTree(leftNode, sonTreePreList, sonTreeLeftVinList, sonTreeRightVinList);
}
} else {
rootNode.left = null;
}
if (rightVinList != null && rightVinList.size() > 0) {
int val = 0;
for (Integer it : preList) {
// 第一次出现的是右子树节点
if (rightVinList.contains(it)) {
val = it;
break;
}
}
TreeNode rightNode = new TreeNode(val);
rootNode.right = rightNode;
ArrayList<Integer> sonTreePreList = new ArrayList<>();
for (Integer it : preList) {
if (rightVinList.contains(it)) {
sonTreePreList.add(it);
}
}
List<Integer> sonTreeLeftVinList = new ArrayList<>();
List<Integer> sonTreeRightVinList = new ArrayList<>();
for (int i = 0; i < rightVinList.size(); i++) {
if (rightVinList.get(i) == sonTreePreList.get(0)) {
sonTreeLeftVinList = rightVinList.subList(0, i);
sonTreeRightVinList = rightVinList.subList(i + 1, rightVinList.size());
}
}
// 递归构建右子树
if (sonTreePreList != null && sonTreePreList.size() > 0) {
buildTree(rightNode, sonTreePreList, sonTreeLeftVinList, sonTreeRightVinList);
}
} else {
rootNode.right = null;
}
}
}
import java.util.*;
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
//思路：前序：根节点，左子树，右子树 中序：左子树，根节点，右子树。 前中，后中都可以唯一确定一棵树，前后无法确定，当子节点只有一个子节点时无法确定这个字节点是左节点还是右节点，只有通过中序才能确认
//前序的第一个元素就是树的根节点，拿到这个节点到中序集合中查找，若找到到了则确定序号index，那么index-1之前的就是左子树，index+1之后的就是右子树，根据类似的方法对左子树进行拆分，分而治之
//自下而上构建左右子树
public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
if (pre == null || vin == null || pre.length == 0 || vin.length == 0) {
return null;
}
return doReConstruct(pre,vin,0,pre.length-1,0,vin.length-1);
}
private TreeNode doReConstruct(int[] pre, int[] vin, int prestart, int preend,int vinstart,int vinend) {
if(prestart > preend || vinstart > vinend) {
return null;
}
int val = pre[prestart];
TreeNode root = new TreeNode(val);
for(int i = vinstart;i<=vinend;i++) {
if (vin[i] == val) {
root.left = doReConstruct(pre, vin, prestart+1, prestart+i-vinstart,vinstart, i-1);
root.right = doReConstruct(pre,vin,prestart+i-vinstart+1, preend, i+1, vinend);
}
}
return root;
}
} 
//递归的思想是把一个大问题分成层层向下的小问题 每一层解决问题的方法都是一样的 我们考虑的就是本层的解决问题逻辑和结束条件
//第一层 [1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]
//第二层(1左子树) [2,4,7],[4,7,2] 每层解决问题的方法都是一样的
//第三层(2左子树) [4,7],[4,7]
//第三层(4右子树) [7],[7]
//每层子树都是一样的解决方式
//ps:先序+中序 中序+后序 都可以确定一棵树 先序+后序不行
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre, int [] vin) {
int m = pre.length;
int n = vin.length;
//中序遍历数组和先序遍历数组长度都不能为空
if (m == 0 ||
n == 0) { //换成&&也一样对 其实这道题里只要它中序遍历为0了 也就不可能有先序遍历的
return null;
}
//计算器a a代表节点node的左子树有多少节点
int a = 0;
//这层子树的根节点必为先序遍历数组第一个位置的节点
TreeNode treeNode = new TreeNode(pre[0]);
for (int i = 0; i < vin.length; i++) {
if (vin[i] != treeNode.val) {
a++;
} else {
//node节点的左子树就是中序遍历node左边的那部分，同时把这左子树这部分的先序遍历数组传进去
treeNode.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, 1 + a),
Arrays.copyOfRange(vin, 0, a));
//node节点的右子树就是中序遍历node右边的那部分，同时把这右子树这部分的先序遍历数组传进去
treeNode.right = reConstructBinaryTree(Arrays.copyOfRange(pre, 1 + a,
pre.length), Arrays.copyOfRange(vin, 1 + a, vin.length));
}
}
//返回这层子树的根节点
return treeNode;
}
} 
public class Solution {
Map<Integer, Integer> map = new HashMap<>();
public TreeNode reConstructBinaryTree(ArrayList<Integer> pre,ArrayList<Integer> vin) {
for(int i=0;i<vin.size();i++){
map.put(vin.get(i), i);
}
return reConstructBinaryTreeWithOffsetSet(pre, 0, pre.size() - 1, 0, vin.size() - 1);
}
public TreeNode reConstructBinaryTreeWithOffsetSet(ArrayList<Integer> pre,int pl, int pr, int vl, int vr){
if(pl>pr || vl>vr) return null;
TreeNode root = new TreeNode(pre.get(pl));
int vm = map.get(pre.get(pl)) - vl;
root.left = reConstructBinaryTreeWithOffsetSet(pre, pl+1, vm+pl, vl, vl+vm-1);
root.right = reConstructBinaryTreeWithOffsetSet(pre, vm+pl+1, pr, vl+vm+1, vr);
return root;
}
} 
public class Solution {
/**
* 前序/中序构造二叉树
* 根|左|右
* 左|右|根
*/
public TreeNode reConstructBinaryTree(List<Integer> pre, List<Integer> vin) {
int[] preorder = pre.stream().mapToInt(i -> i).toArray();
int[] inorder = vin.stream().mapToInt(i -> i).toArray();
return doBuildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
public TreeNode doBuildTree(int[] preorder, int i, int j, int[] inorder, int p, int r) {
if (i > j) return null;
TreeNode root = new TreeNode(preorder[i]);
// 在中序遍历结果inorder中,查询preorder[i]所在的位置q
// [p,q-1] q [q+1,r]
int q = p;
while (inorder[q] != preorder[i]) {
q++;
}
int leftTreeSize = q - p; // 左右子树大小
// 构建左子树
TreeNode leftNode = doBuildTree(preorder, i + 1, i + leftTreeSize, inorder, p, q - 1);
// 构建右子树
TreeNode rightNode = doBuildTree(preorder, i + leftTreeSize + 1, j, inorder, q + 1, r);
// 根据root、左子树、右子树构建树 [i+1, j]
root.left = leftNode;
root.right = rightNode;
return root;
}
} 
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre, int [] vin) {
if (pre.length == 0 || vin.length == 0)
return null;
int i = 0;
TreeNode head = new TreeNode(pre[0]);
while (vin[i] != pre[0]) {
i++;
}
head.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1),
Arrays.copyOfRange(vin, 0, i));
head.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length),
Arrays.copyOfRange(vin, i + 1, vin.length));
return head;
}
} 
import java.util.*;
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
if(pre==null||pre.length==0||vin==null||vin.length==0){
return null;
}
TreeNode node=new TreeNode(pre[0]);
int log=-1;
for(int i=0;i<vin.length;i++){
if(pre[0]==vin[i]){
log=i;
break;
}
}
int len=log;
node.left=reConstructBinaryTree(Arrays.copyOfRange(pre,1,1+len),
Arrays.copyOfRange(vin,0,log));
node.right=reConstructBinaryTree(Arrays.copyOfRange(pre,len+1,pre.length),
Arrays.copyOfRange(vin,log+1,vin.length));
return node;
}
// public TreeNode show(int[] pre,int[] vin,TreeNode node){
// TreeNode val=
// }
} 
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] in) { TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1); return root; } //前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6} private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) { if(startPre>endPre||startIn>endIn) return null; TreeNode root=new TreeNode(pre[startPre]); for(int i=startIn;i<=endIn;i++) if(in[i]==pre[startPre]){ root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1); root.right=reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn); break; } return root; } }