参考Macho0723的博客，网址：https://blog.csdn.net/qq_34154570/article/details/82700094
已知前序、中序，求二叉树和后序遍历结果
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。（剑指offer原题）
1 1 1 1 1
472 5386 2 5386 2 5386 2 3 2 3
47 4 4 5 86 4 5 6
7 7 7 8
具体代码为：
方法：
Arrays.copyOfRange(T[ ] original,int from,int to) //将一个原始的数组original，从下标from开始复制，复制到上标to，生成一个新的数组。即复制范围为：[from,to)
package algorithm;
import java.util.Arrays;
/* 参考Macho0723的博客，网址：https://blog.csdn.net/qq_34154570/article/details/82700094
已知前序、中序，求二叉树和后序遍历结果
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。（剑指offer原题）
1 1 1 1 1
472 5386 2 5386 2 5386 2 3 2 3
47 4 4 5 86 4 5 6
7 7 7 8
具体代码为： * */
public class Tree {
class TreeNode{ int value; TreeNode left; TreeNode right; TreeNode(int value1){ this.value=value1; } } public static TreeNode createTree(int[] pre,int[] mid){ if(pre==null||mid==null||pre.length==0||mid.length==0){ return null; } TreeNode node=new Tree().new TreeNode(pre[0]); for(int i=0;i<mid.length;i++){ if(pre[0]==mid[i]){//相同 // node.left= //其中方法Arrays.copyOfRange(T[ ] original,int from,int to) //原始数组original，从from(包括)开始复制，复制到上标to（不包括），生成一个新的数组。即复制范围为：[from,to) node.left = createTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(mid, 0, i)); node.right = createTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(mid, i + 1, mid.length));
} } return node; } //二叉树的遍历--前序遍历 先根-左->右 public static void preTravel(TreeNode node){ if(node==null){ return; } printNode(node); preTravel(node.left); preTravel(node.right); } //二叉树的遍历--中序遍历 先左->根->右 public static void midTravel(TreeNode node){ if(node==null){ return; } midTravel(node.left); printNode(node); midTravel(node.right); } //二叉树的遍历--后序遍历 先左->右->根 public static void lastTravel(TreeNode node){ if(node==null){ return; } lastTravel(node.left); lastTravel(node.right); printNode(node); } private static void printNode(TreeNode node) { // TODO Auto-generated method stub System.out.print(" "+node.value); }
public static void main(String[] args) { // TODO Auto-generated method stub int[] pre={1,2,4,7,3,5,6,8}; int[] mid={4,7,2,1,5,3,8,6}; TreeNode node=createTree(pre,mid); System.out.println("前序遍历："); preTravel(node); System.out.println("\n中序遍历："); midTravel(node); System.out.println("\n后序遍历："); lastTravel(node); }
}
前序遍历： 1 2 4 7 3 5 6 8 中序遍历： 4 7 2 1 5 3 8 6 后序遍历： 7 4 2 5 8 6 3 1
