思路：要想完成这道编程题，首先你得很清楚，如何通过一个前序遍历序列和一个中序遍历序列，重建一棵二叉树？如果你不清楚这个过程，没关系，我尽自己最大能力去讲解。如果还是不懂，可以考虑上网搜一些图文并茂的资料，可能会好很多。
- 可以这样认为，前序遍历序列中的每一个节点，都是根节点(叶子节点可以看作根节点，只不过是左右孩子都为 null 的根节点罢了)。
- 然后，我们每一次从前序遍历序列中取出一个"根节点"，在中序遍历序列中找到它所在的位置。
- 以它为中心，可以将整个中序遍历序列分成两部分(如果此时这个点在中序遍历序列的边上，可以认为它其中的一部分为空)，左半边是它的左子树，右半边是它的右子树。
- 接着，分别对它的左半边和右半边重复上述的操作(再从前序遍历序列中获取一个“根节点”，对它的左半边进行切分)，最终我们就可以重建出一棵二叉树。
注：本人表达能力有限，实在看不懂的，可以自己动手画一画，或者上网搜更好的资料学习。
系统给定的函数
// 一些特殊情况的处理
if (0 == pre.length) { // 如果 pre 数组的长度为 0，直接返回一个 null 即可
return null;
}
if (1 == pre.length) { // 如果 pre 数组的长度为 1，直接返回以 pre 数组中唯一的一个数为 val 值的 TreeNode 即可
return new TreeNode(pre[0]);
}
// 思路：要想完成这道编程题，首先你得很清楚，如何通过一个前序遍历序列和一个中序遍历序列，重建一棵二叉树？如果你不清楚这个过程，没关系，我尽自己最大能力去讲解。如果还是不懂，可以考虑上网搜一些图文并茂的资料，可能会好很多。
// 可以这样认为，前序遍历序列中的每一个节点，都是根节点(叶子节点可以看作根节点，只不过是左右孩子都为 null 的根节点罢了)。
// 然后，我们每一次从前序遍历序列中取出一个"根节点"，在中序遍历序列中找到它所在的位置。
// 以它为中心，可以将整个中序遍历序列分成两部分(如果此时这个点在中序遍历序列的边上，可以认为它其中的一部分为空)，左半边是它的左子树，右半边是它的右子树。
// 接着，分别对它的左半边和右半边重复上述的操作(再从前序遍历序列中获取一个“根节点”，对它的左半边进行切分)，最终我们就可以重建出一棵二叉树。
// 注：本人表达能力有限，实在看不懂的，可以自己动手画一画，或者上网搜更好的资料学习。
// 好啦，当你已经清楚如何通过一个前序遍历序列和一个中序遍历序列，重建一棵二叉树后，我们就可以考虑如何编写代码了。
// 1）由于我们每一次都要从前序遍历序列中获取一个"根节点"，因此我们将题目传进来的 int 数组转换成 LinkedList 进行存储。这样，我们就可以保证每一次的递归造树，队列的队头都是当前树的根节点
LinkedList<Integer> linkedList = new LinkedList<>();
// 2）ArrayList 数组存放的是中序遍历序列。(没啥原因，单纯就是用得习惯，哈哈)
ArrayList<Integer> arrayList = new ArrayList<>();
// 3）HashMap 存放的是，在中序遍历序列中，每个节点和它的下标一一对应的关系。注意，这个 HashMap 很重要，关系到你从前序遍历序列中获取到一个"根节点"后，如何在中序遍历序列中找到它的位置！！！
HashMap<Integer, Integer> hashMap = new HashMap<>();
// 以下这几段代码就没什么好说的啦，无非就是将题目给的两个 int 数组，分别转换成 LinkedList 和 ArrayList，同时构造出 HashMap，然后调用递归函数，最后再返回根节点。
for (int tmp : pre) {
linkedList.add(tmp);
}
for (int i = 0; i < vin.length; i++) {
arrayList.add(vin[i]);
hashMap.put(vin[i], i);
}
TreeNode root = process(linkedList, arrayList, hashMap, 0, arrayList.size() - 1);
return root;
}
接下来的递归函数，才是整个算法的核心！！！重点讲解！！！
- 首先，我们应该考虑这个递归函数是要做什么的，先不要考虑递归的终止条件。
- 当你以下代码都搞懂之后，我们就可以考虑如何终止递归了。
- 前面我并没有讲清楚，所谓的分割中序遍历序列，并不是真的分割了 ArrayList 这个数组。准确来说，这数组无论哪一次递归，都是同一个。
- 所谓的切割，我们是通过 start 和 end 这两个值来定义的，它限制了当前递归中 ArrayList 数组的范围。
- 也就是说，ArrayList 永远是你的 ArrayList，它不会变，变的只是 start 和 end，它限制了你当前递归中 ArrayList 的检索范围！！！
- 既然如此，递归的终止条件就可以通过 start 和 end 来实现了。(具体为什么满足这个，就是终止，要自己调试，才能明白。主要是我说不清楚，哈哈)
递归函数的实现如下(代码里还有很详细的注释哦)
* 参数说明
* pre 前序遍历序列
* vin 中序遍历序列
* nodeIndexs 就是上面我们构造的 HashMap
* start、end 共同表示的是，当前中序遍历序列的范围
*/
// 以下详细讲解以下这个递归函数的思路(记得每一个参数的含义以及它的变量名)
public TreeNode process(LinkedList<Integer> pre, ArrayList<Integer> vin, HashMap<Integer, Integer> nodeIndexs, int start, int end) {
// 首先，我们应该考虑这个递归函数是要做什么的，先不要考虑递归的终止条件。
// 当你以下代码都搞懂之后，我们就可以考虑如何终止递归了。
// 前面我并没有讲清楚，所谓的分割中序遍历序列，并不是真的分割了 ArrayList 这个数组。准确来说，这数组无论哪一次递归，都是同一个。
// 所谓的切割，我们是通过 start 和 end 这两个值来定义的，它限制了当前递归中 ArrayList 数组的范围。
// 也就是说，ArrayList 永远是你的 ArrayList，它不会变，变的只是 start 和 end，它限制了你当前递归中 ArrayList 的检索范围！！！
// 既然如此，递归的终止条件就可以通过 start 和 end 来实现了。(具体为什么满足这个，就是终止，要自己调试，才能明白。主要是我说不清楚，哈哈)
if (start > end || pre.isEmpty()) {
return null;
}
if (start == end) {
return new TreeNode(pre.poll());
}
// 然后，pre 出队一个数值，以这个数值构造一个 TreeNode 节点，同时，通过 nodeIndexs，找到这个节点在中序遍历序列中的下标。
// 接下来我们要做的，其实就是构造一棵以这个节点为根节点的一棵二叉树。
int val = pre.poll();
TreeNode root = new TreeNode(val);
int index = nodeIndexs.get(val);
// 接着，以这个节点为中心，将中序遍历序列切割成两部分，将这两部分分别丢给递归函数，让递归函数帮你把左子树和右子树构造好，并返回左右孩子节点
TreeNode leftNode = process(pre, vin, nodeIndexs, start, index - 1);
TreeNode rightNode = process(pre, vin, nodeIndexs, index + 1, end);
// 最后，我们再将根节点与左右孩子关联起来，并返回。
root.left = leftNode;
root.right = rightNode;
return root;
// 关于递归，很抱歉，其实我也不是很清楚，一般都是凭经验、凭感觉写的。像上面两个递归(构造左右子树)，你只需要知道，将所有参数丢进去，系统就会帮你构造出左右子树了，并把左右孩子节点返回给你。具体的底层原理，不要理会(我是真的不是很懂，挠头)
}
完整的代码实现如下
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
// 一些特殊情况的处理
if (0 == pre.length) { // 如果 pre 数组的长度为 0，直接返回一个 null 即可
return null;
}
if (1 == pre.length) { // 如果 pre 数组的长度为 1，直接返回以 pre 数组中唯一的一个数为 val 值的 TreeNode 即可
return new TreeNode(pre[0]);
}
// 思路：要想完成这道编程题，首先你得很清楚，如何通过一个前序遍历序列和一个中序遍历序列，重建一棵二叉树？如果你不清楚这个过程，没关系，我尽自己最大能力去讲解。如果还是不懂，可以考虑上网搜一些图文并茂的资料，可能会好很多。
// 可以这样认为，前序遍历序列中的每一个节点，都是根节点(叶子节点可以看作根节点，只不过是左右孩子都为 null 的根节点罢了)。
// 然后，我们每一次从前序遍历序列中取出一个"根节点"，在中序遍历序列中找到它所在的位置。
// 以它为中心，可以将整个中序遍历序列分成两部分(如果此时这个点在中序遍历序列的边上，可以认为它其中的一部分为空)，左半边是它的左子树，右半边是它的右子树。
// 接着，分别对它的左半边和右半边重复上述的操作(再从前序遍历序列中获取一个“根节点”，对它的左半边进行切分)，最终我们就可以重建出一棵二叉树。
// 注：本人表达能力有限，实在看不懂的，可以自己动手画一画，或者上网搜更好的资料学习。
// 好啦，当你已经清楚如何通过一个前序遍历序列和一个中序遍历序列，重建一棵二叉树后，我们就可以考虑如何编写代码了。
// 1）由于我们每一次都要从前序遍历序列中获取一个"根节点"，因此我们将题目传进来的 int 数组转换成 LinkedList 进行存储。这样，我们就可以保证每一次的递归造树，队列的队头都是当前树的根节点
LinkedList<Integer> linkedList = new LinkedList<>();
// 2）ArrayList 数组存放的是中序遍历序列。(没啥原因，单纯就是用得习惯，哈哈)
ArrayList<Integer> arrayList = new ArrayList<>();
// 3）HashMap 存放的是，在中序遍历序列中，每个节点和它的下标一一对应的关系。注意，这个 HashMap 很重要，关系到你从前序遍历序列中获取到一个"根节点"后，如何在中序遍历序列中找到它的位置！！！
HashMap<Integer, Integer> hashMap = new HashMap<>();
// 以下这几段代码就没什么好说的啦，无非就是将题目给的两个 int 数组，分别转换成 LinkedList 和 ArrayList，同时构造出 HashMap，然后调用递归函数，最后再返回根节点。
for (int tmp : pre) {
linkedList.add(tmp);
}
for (int i = 0; i < vin.length; i++) {
arrayList.add(vin[i]);
hashMap.put(vin[i], i);
}
TreeNode root = process(linkedList, arrayList, hashMap, 0, arrayList.size() - 1);
return root;
}
/*
* 参数说明
* pre 前序遍历序列
* vin 中序遍历序列
* nodeIndexs 就是上面我们构造的 HashMap
* start、end 共同表示的是，当前中序遍历序列的范围
*/
// 以下详细讲解以下这个递归函数的思路(记得每一个参数的含义以及它的变量名)
public TreeNode process(LinkedList<Integer> pre, ArrayList<Integer> vin, HashMap<Integer, Integer> nodeIndexs, int start, int end) {
// 首先，我们应该考虑这个递归函数是要做什么的，先不要考虑递归的终止条件。
// 当你以下代码都搞懂之后，我们就可以考虑如何终止递归了。
// 前面我并没有讲清楚，所谓的分割中序遍历序列，并不是真的分割了 ArrayList 这个数组。准确来说，这数组无论哪一次递归，都是同一个。
// 所谓的切割，我们是通过 start 和 end 这两个值来定义的，它限制了当前递归中 ArrayList 数组的范围。
// 也就是说，ArrayList 永远是你的 ArrayList，它不会变，变的只是 start 和 end，它限制了你当前递归中 ArrayList 的检索范围！！！
// 既然如此，递归的终止条件就可以通过 start 和 end 来实现了。(具体为什么满足这个，就是终止，要自己调试，才能明白。主要是我说不清楚，哈哈)
if (start > end || pre.isEmpty()) {
return null;
}
if (start == end) {
return new TreeNode(pre.poll());
}
// 然后，pre 出队一个数值，以这个数值构造一个 TreeNode 节点，同时，通过 nodeIndexs，找到这个节点在中序遍历序列中的下标。
// 接下来我们要做的，其实就是构造一棵以这个节点为根节点的一棵二叉树。
int val = pre.poll();
TreeNode root = new TreeNode(val);
int index = nodeIndexs.get(val);
// 接着，以这个节点为中心，将中序遍历序列切割成两部分，将这两部分分别丢给递归函数，让递归函数帮你把左子树和右子树构造好，并返回左右孩子节点
TreeNode leftNode = process(pre, vin, nodeIndexs, start, index - 1);
TreeNode rightNode = process(pre, vin, nodeIndexs, index + 1, end);
// 最后，我们再将根节点与左右孩子关联起来，并返回。
root.left = leftNode;
root.right = rightNode;
return root;
// 关于递归，很抱歉，其实我也不是很清楚，一般都是凭经验、凭感觉写的。像上面两个递归(构造左右子树)，你只需要知道，将所有参数丢进去，系统就会帮你构造出左右子树了，并把左右孩子节点返回给你。具体的底层原理，不要理会(我是真的不是很懂，挠头)
}
}
京公网安备 11010502036488号