Java 剑指offer 面试题7：重建二叉树
给出二叉树的中序和前序遍历，重建该二叉树，或者给出中序和后序遍历，重建二叉树。
思路：
对于无论是前序+中序重建二叉树，还是后序+中序
中序都是来提供左右子树的划分，而前序和后序是来判断根节点
先定义树的结构体
public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x){val = x;}
}
根据中序+前序重构二叉树代码：
import java.util.Arrays;public class reConBinaryTreeByPreAndIn {public static TreeNode conBinaryTree(int[] pre,int[] in){if(pre==null||in==null){return null;}if(pre.length==0||in.length==0){return null;}if(pre.length!=in.length){return null;}//根据先序，可以直接确定根的值TreeNode root = new TreeNode(pre[0]);for(int i=0;i根据中序+后序重构二叉树代码：
import java.util.Arrays;public class reConBinaryTreeByPostAndIn {public static TreeNode conBinaryTree(int[] post,int[] in){if(post==null||in==null){return null;}if(post.length==0||in.length==0){return null;}if(post.length!=in.length){return null;}TreeNode root = new TreeNode(post[post.length-1]);for(int i=0;i在递归方法中调用了Arrays.copyOfRange（int[] m ,from,to）这个函数，是将m数组由from到to重新复制一份，是包括from不包括to，Arrays.copyOfRange（（int[] m ,0,0））=[] 而也就是说递归的边界是当递归函数的参数中，（int[] m ,A,B），当A=B时，也就是 当pre和in 或者 post和in 两个数组一样时，他们的下次递归参数就成了 [] 因此也就返回null 说明该节点没有子节点了。递归结束。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！