PS：《剑指offer》是很多同学找工作都会参考的一本面试指南，同时也是一本算法指南（为什么它这么受欢迎，主要应该是其提供了一个循序渐进的优化解法，这点我觉得十分友好）。现在很多互联网的算法面试题基本上可以在这里找到影子，为了以后方便参考与回顾，现将书中例题用Java实现（第二版），欢迎各位同学一起交流进步。
GitHub： https://github.com/Uplpw/SwordOffer。
完整题目链接： https://blog.csdn.net/qq_41866626/article/details/120415258
目录
1 题目描述
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如：先序遍历为[3,9,20,15,7]，中序遍历为 [9,3,15,20,7]，其对应的二叉树如下
3
/ \
9 20
/ \
15 7
leetcode链接： 重建二叉树（以下代码已测试，提交通过）
2 测试用例
一般是考虑功能用例，特殊（边缘）用例或者是反例，无效测试用例这三种情况。甚至可以从测试用例寻找一些规律解决问题，同时也可以让我们的程序更加完整鲁棒。
（1）功能用例：完全与非完全二叉树。
（2）边缘用例：只有一个节点，只有左节点，只有右节点。
（3）无效用例：树为空，对应数组为空。
3 思路
分析：
从数据结构中可知，根据二叉树的先序与中序遍历结果可以唯一的重建二叉树（另外根据后序与中序也可以唯一的重建二叉树）。需要注意的是：前提条件是，树中的任意两个节点值不能相同
重建二叉树，最直接的想法是找到根节点，以及左右子树的节点集合，然后对每个节点不断递归即可。下面考虑如何找到根节点以及左右子树节点集合，并以上例举例（先序遍历为[3,9,20,15,7]，中序遍历为 [9,3,15,20,7]）。
- 根节点：根据先序遍历的特点，第一个节点即是根节点（值为3的节点为根节点）。
- 左右子树集合：根据中序遍历特点，根节点左边的节点集合为左子树（[ 9 ]），根节点右边的节点集合为右子树（[15,20,7]）
下面是递归解法思路与具体过程、以及时间空间复杂度比较。
解法1：递归实现
- 递归终止条件：当输入先序、中序遍历结果数组没有元素时，说明左/右子树构建完成，直接返回null即可。
- 划分左右子树：根据先序遍历的第一个节点，找到中序遍历与之相同的节点，左边是左子树，右边是右子树
- 构建根节点：根据先序遍历的第一个节点构建新节点，即当前根节点root
- 递归构建左右子树：更新先序、中序遍历结果数组递归调用。
- 返回值：最后回溯返回的根节点即整个二叉树的根节点。
注意： 比较简单直接地方式是每次递归左右子树时，可以新建左右子树数组传进去进行处理，但会浪费时间与空间，优化方式是使用下标以及左右子树节点数量来代替，具体细节见代码。
时间空间复杂度： O ( n ) , O ( n ) O(n),O(n) O(n),O(n)
4 代码
二叉树结构类：
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
算法实现：
public class ConstructBinaryTree {
/**
* @param preorder：先序遍历结果
* @param inorder：中序遍历结果
* @return : 构建完成的二叉树根节点
*/
public static TreeNode buildTree(int[] preorder, int[] inorder) {
// 无效数据判断
if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0 || preorder.length != inorder.length) {
return null;
}
// 递归调用
return constructCore(preorder, 0, inorder, 0, preorder.length);
}
/**
* @param preorder：当前子树的先序遍历结果（实际上还是整个结果，使用preStart作为标志）
* @param preStart：记录子树先序遍历的开始
* @param inorder：当前子树的中序遍历结果（实际上还是整个结果，使用inStart作为标志）
* @param inStart：记录子树中序遍历的开始
* @param length：当前子树的节点数量
* @return
*/
public static TreeNode constructCore(int[] preorder, int preStart, int[] inorder, int inStart, int length) {
// 左右子树集合为空，构建完成直接返回
if (length == 0) {
return null;
}
int index = -1;
// 查找根节点在中序遍历中的索引位置
for (int i = inStart; i < inStart + length; i++) {
if (preorder[preStart] == inorder[i]) {
index = i;
break;
}
}
// 左子树的节点数量
int preorder_length = index - inStart;
// 构建根节点
TreeNode root = new TreeNode(preorder[preStart]);
/*
递归左子树构建
参数preStart：由于是构建左子树，先序第一个节点是根节点，所以左子树集合开始索引需要+1
参数inStart：由于中序遍历左边结果一定是左子树，所以不进行更新
参数length：左子树节点数量=preorder_length
*/
root.left = constructCore(preorder, preStart + 1, inorder, inStart, preorder_length);
/*
递归右子树构建
参数preStart：由于是构建右子树，右子树集合开始的索引在 根节点开始索引+左子树节点数量+1
参数inStart：由于中序遍历中根节点右边的数据一定是右节点，所以右子树开始索引是 index+1
参数length：右子树节点数量=length - preorder_length - 1（当前子树节点数量-左子树节点数量-根节点）
*/
root.right = constructCore(preorder, preStart + preorder_length + 1, inorder, index + 1,
length - preorder_length - 1);
return root;
}
}
参考
在解决本书例题时，参考了一些大佬的题解，比如leetcode上的官方、K神，以及其他的博客，在之后的每个例题详解后都会给出参考的思路或者代码链接，同学们都可以点进去看看！
本例题参考：
https://www.jianshu.com/p/ddc50561dda5
本文如有什么不足或不对的地方，欢迎大家批评指正，最后希望能和大家一起交流进步、拿到心仪的 offer !!!