写在前面：
为了增长一下自己的数据结构能力，也为了面试准备，准备将剑指Offer做一下，并与各位分享，希望各位可以对代码以及思路提提建议，欢迎志同道合者，谢谢。
题目：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路：
首先讲一下什么是二叉树的中序，前序，后序遍历，大家也可以看看我这篇二叉树相关,中序，前序，后序，遍历，大家只需要记住这个是相对于根节点的就好，左子树和右子树的顺序不变，比如说前序遍历，也就是先打印根节点，然后打印左子树然后是右子树，中序就是先打印左子树，然后打印根节点，然后打印右子树，那么后序想必大家都知道了吧，左子树，右子树，根节点，
好了，知道了什么是前序，中序，后序，，那么我们看看这三种排序有啥特点呢， 前序已经说了，先打印根节点，也就是前序按顺序来，都是根节点， 那么中序呢，先打印左子树，然后打印根节点， 那么我们能不能根据前序的根节点在中序中找到他的左子树呢，还有右子树，举个栗子
前序 1,2,4,7,3,5,6,8
中序 4,7,2,1,5,3,8,6
首先1是根节点，那么中序中1的左边(4,7,2)全是1的左子树的节点，右边(5,3,8,6)全都是右子树节点，然后我们看左子树，根节点是2，中序中2的左边(4,7)都是2的左子树节点，2的右边没有数据，说明他没有右子树，依次类推,
注意，每次找到根节点之后，那么就将中序从根节点分为两部分，左边是左子树，右边是右子树，然后分别进行递归，
好了，现在正式进入代码环节
package com.itzmn.offer;
import javax.swing.tree.TreeNode;
/**
* @Auther: 张梦楠
* @Date: 2018/7/28 08:12
* 简书：https://www.jianshu.com/u/d611be10d1a6
* 码云：https://gitee.com/zhangqiye
* @Description: 重建二叉树
*
* 输入前序与中序，还原出二叉树，
*
* 前序的每一个都是根节点，根据根节点在中序中寻找，左边的就是左子树的节点，右边的就右子树的节点
*
*/
public class Offer4 {
public static void main(String[] args) {
int[] pre = {1,2,4,7,3,5,6,8};
int[] in = {4,7,2,1,5,3,8,6};
TreeNode treeNode = new Offer4().reConstructBinaryTree(pre, in);
new Offer4().printpreTree(treeNode);
}
public TreeNode reConstructBinaryTree(int [] pre, int [] in) {
if (pre.length == 0 || in.length == 0 || pre.length != in.length){
System.out.println("您输入的数据不合法");
return null;
}
return createBinaryTree(pre,0,pre.length-1,in , 0 , in.length-1);
}
/**
*
* @param pre 前序遍历
* @param preB 前序遍历开始的坐标
* @param preE 前序遍历最终坐标
* @param in 中序遍历
* @param inB 中序遍历开始位置
* @param inE 中序遍历结束位置
* @return 返回二叉树根节点
*/
private TreeNode createBinaryTree(int[] pre, int preB, int preE, int[] in, int inB, int inE) {
if (preB >preE){
return null;
}
/**
* 从前序遍历中寻找根节点
* 根据根节点在中序遍历中找到左右子树
*/
//这是根节点的值，
int value = pre[preB];
int index = inB;
// 在中序遍历中找到这个根节点
while (index <= inE && in[index] != value){
index++;
}
// 判断中序中是否有这个根节点
if (index > inE){
throw new RuntimeException("输入的数据有问题");
}
TreeNode treeNode = new TreeNode(value);
/**
* 构建左子树
*/
treeNode.left = createBinaryTree(pre,preB+1,preB+index-inB,in,inB,index-1);
treeNode.right = createBinaryTree(pre,preB+index-inB+1,preE,in,index+1,inE);
return treeNode;
}
/**
* 输出数的前序遍历
* @param treeNode
*/
public void printpreTree(TreeNode treeNode){
System.out.println(treeNode.val);
if (treeNode.left != null){
printpreTree(treeNode.left);
}
if (treeNode.right != null){
printpreTree(treeNode.right);
}
}
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
}
希望大家可以多多指点，优化一下，
QQ群：552113611
网友评论