剑指Offer面试题：4.重建二叉树
一、题目
————————————————
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1, 2, 4, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8, 6}，则重建出其二叉树并输出它的头结点。
二、思路
————————————————
前序遍历第一个值就是根结点的值，根据该值在中序遍历的位置，可以轻松找出该根结点左右子树的前序遍历和中序遍历，之后又可以用同样方法构建左右子树，所以该题可以采用递归的方法完成。
刚开始思考的时候，想的是构建一个遍历函数，输入为前序和中序遍历的数组，输出为根结点。但是这样的话每次都需要构建子树的数组，非常麻烦。
之后想到，该函数的输入不一定要用数组，因为最初的前序和中序遍历数组已经有了，就直接用该数组的下标来表示子树的数组即可。
即构建函数construct(int[] pre, int[] in, int pStart, int pEnd, int iStart, int iEnd)，pre和in始终用最初前序遍历和中序遍历的数组代入，pStart、pEnd代表当前树的前序数组开始和结束位置，iStart、iEnd代表中序数组开始和结束位置。
————————————————
————————————————
三、解决问题
测试用例
1.正常二叉树
2.左斜树
3.右斜树
4.单个结点
5.数组为空
package swordoffer;
/**
* @author LQ
* @version 1.0
* @date 2020-03-13 15:56
*/
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
package swordoffer;
/**
* @author LQ
* @version 1.0
* @date 2020\3\12 0012 17:06
*/
import java.util.HashMap;
import java.util.Map;
/**
* 题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回
*/
public class Solution04 {
public static void main(String[] args) {
System.out.println("==============================");
Solution04 sword = new Solution04();
sword.test1();
System.out.println("==============================");
sword.test2();
System.out.println("==============================");
sword.test3();
System.out.println("==============================");
sword.test4();
System.out.println("==============================");
sword.test5();
System.out.println("==============================");
}
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if (pre == null || in == null || pre.length <= 0 || in.length <= 0 || pre.length != in.length) {
throw new RuntimeException("数组不符合规范！");
}
return construct(pre, in, 0, pre.length - 1, 0, in.length - 1);
}
/**
*
* @Description 由前序遍历序列和中序遍历序列得到根结点
* pre、in：始终用最初的前序遍历和中序遍历数组代入
* pStart、pEnd：当前树的前序数组开始和结束位置
* iStart、iEnd：中序数组开始和结束位置
*/
public TreeNode construct(int[] pre, int[] in, int pStart, int pEnd, int iStart, int iEnd) {
//1.根据前序遍历序列的第一个数字创建根结点
TreeNode root = new TreeNode(pre[pStart]);
//前序遍历与中序遍历只有一个结点，返回根结点
if (pStart == pEnd && iStart == iEnd) {
if (pre[pStart] != in[iStart]){
throw new RuntimeException("数组不符合规范！");
}
return root;
}
//2.在中序遍历序列中找到根结点的位置
int index = iStart; // 用于记录中序遍历序列中根结点的位置
while (root.val != in[index] && index <= iEnd) {
index++;
}
//若找到结点位置大于中序遍历的长度,数组不符合规范
if (index > iEnd){
throw new RuntimeException("数组不符合规范！");
}
//3.在前序遍历和中序遍历的序列中划分左、右子树结点的值之后，我们可以递归调用函数
int leftLength = index - iStart;
if (leftLength > 0) {
//划分左子树
root.left = construct(pre, in, pStart + 1, pStart + leftLength, iStart, index - 1);
}
if (leftLength < iEnd - iStart) {
//划分右子树
root.right = construct(pre, in, pStart + leftLength + 1, pEnd, index + 1, iEnd);
}
return root;
}
//前序遍历-根=>左=>右
private void preOrderTraverse(TreeNode node) {
if (node == null){
return;
}
System.out.print(node.val + " ");//根
preOrderTraverse(node.left);//左
preOrderTraverse(node.right);//右
}
//中序遍历-左=>根=>右
private void inOrderTraverse(TreeNode node) {
if (node == null){
return;
}
inOrderTraverse(node.left);//左
System.out.print(node.val + " ");//根
inOrderTraverse(node.right);//右
}
//后序遍历-左=>右=>根
private void postOrderTraverse(TreeNode node) {
if (node == null){
return;
}
postOrderTraverse(node.left);//左
postOrderTraverse(node.right);//右
System.out.print(node.val + " ");//根
}
/**
* 正常二叉树
*/
public void test1() {
int[] pre = { 1, 2, 4, 7, 3, 5, 6, 8 };
int[] in = { 4, 7, 2, 1, 5, 3, 8, 6 };
TreeNode root = reConstructBinaryTree(pre, in);
System.out.println("test1:");
System.out.print("前序遍历-根=>左=>右：");
preOrderTraverse(root);
System.out.println();
System.out.print("中序遍历-左=>根=>右：");
inOrderTraverse(root);
System.out.println();
System.out.print("后序遍历-左=>右=>根：");
postOrderTraverse(root);
System.out.println();
}
/**
* 左斜树
*/
public void test2() {
int[] pre = { 1, 2, 3, 4, 5 };
int[] in = { 5, 4, 3, 2, 1 };
TreeNode root = reConstructBinaryTree(pre, in);
System.out.println("test2:");
System.out.print("前序遍历-根=>左=>右：");
preOrderTraverse(root);
System.out.println();
System.out.print("中序遍历-左=>根=>右：");
inOrderTraverse(root);
System.out.println();
System.out.print("后序遍历-左=>右=>根：");
postOrderTraverse(root);
System.out.println();
}
/**
* 右斜树
*/
public void test3() {
int[] pre = { 1, 2, 3, 4, 5 };
int[] in = { 1, 2, 3, 4, 5 };
TreeNode root = reConstructBinaryTree(pre, in);
System.out.println("test3:");
System.out.print("前序遍历-根=>左=>右：");
preOrderTraverse(root);
System.out.println();
System.out.print("中序遍历-左=>根=>右：");
inOrderTraverse(root);
System.out.println();
System.out.print("后序遍历-左=>右=>根：");
postOrderTraverse(root);
System.out.println();
}
/**
* 单个结点
*/
public void test4() {
int[] pre = { 1 };
int[] in = { 1 };
TreeNode root = reConstructBinaryTree(pre, in);
System.out.println("test4:");
System.out.print("前序遍历-根=>左=>右：");
preOrderTraverse(root);
System.out.println();
System.out.print("中序遍历-左=>根=>右：");
inOrderTraverse(root);
System.out.println();
System.out.print("后序遍历-左=>右=>根：");
postOrderTraverse(root);
System.out.println();
}
/**
* 数组为空
*/
public void test5() {
int[] pre = {};
int[] in = {};
TreeNode root = reConstructBinaryTree(pre, in);
System.out.println("test5:");
System.out.print("前序遍历-根=>左=>右：");
preOrderTraverse(root);
System.out.println();
System.out.print("中序遍历-左=>根=>右：");
inOrderTraverse(root);
System.out.println();
System.out.print("后序遍历-左=>右=>根：");
postOrderTraverse(root);
System.out.println();
}
}
输出结果：
努力也是需要学习的，别再让你的努力，只感动了自己！愿你的每一次努力，都能为自己和别人创造价值。
Java基础 文章被收录于专栏
建立本人的Java基础技术栈积累库
网易公司福利 161人发布