2023年6月22日发(作者：)

Java实现⼀直⼆叉树前序和中序，还原⼆叉树前序：ABCDEF中序：CBAEDF求原来的⼆叉树前序：根左右中序：左根右后序：左右根根据前序和中序还原⼆叉树： 思路：根据前序知道⼆叉树的根包括各个⼦树的根，然后再在中序⾥⾯找到根的那个，前⾯的都是左⼦树，⽽后⾯的都是右⼦树，然后⽤递归的思想再处理每个⼦树的那部分。思路还是⼀样的。部分代码；代码说明：代码取⾃⽜客⽹ 欲风package ioffer;public class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode(int x){ = x;}}-----------------------------------package ioffer;/* * 根据⼆叉树的先序和中序重新构建⼆叉树 * 前序：pre[] * 中序：in[] * public class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode(int x){ = x;} *} * */public class CreateTree {public TreeNode reConstructBinaryTree(int [] pre,int [] in) {TreeNode root = createTree(pre,0,-1,in,0,-1);return root;}private TreeNode createTree(int[] pre, int startpre, int endpre, int[] in, int startin, int endin) {// TODO Auto-generated method stubif(startpre>endpre || startin>endin){return null;}TreeNode root = new TreeNode(pre[startpre]);//树的根for(int i = startin;i<=endin;i++){if(pre[startpre] == in[i]){ = createTree(pre,startpre+1,startpre+i,in,startin,i-1);//去除掉已经确定的根节点 = createTree(pre,i-startin+startpre+1,endpre,in,i+1,endin);//说明：i-startin 是i这个元素的左⼦树 解释来⾃ 深⽔的鱼}}return root;}}