题解 | #重建二叉树#

这是我目前做过最难，花的时间最多的程序题。

1.两天前的下午，我开始思考这道题，一开始想的是先求得树的深度，再把树的两个边还原，然后在根据大小关系，往里面插入元素。后来发现需要的程序太大。根本实现不了。

2.然后思考很久之后，我发现前序的数列相邻两个元素之间有血缘关系，要么是兄弟，要么是父子；然后发现中序数组的前后顺序，就是树的左右关系，在前的元素一定在左边。然后开始写代码，写着写着，前序数组的相邻两个节点不一定有血缘关系，而且有血缘关系的节点，不一定在元素前后，可能相邻若干个。

3.然后我发现，如果从中序数组的根节点开始，找左儿子，如果有左儿子，一定是前序数组的后一位，如果中序数组的左边不存在前序数组的后一位，那就没有左儿子。这里不能简单的判断如果该元素在中序数组的位置只要不为0就有左节点。因为左边可能都是他的父亲辈的。不是他儿子。但是，如果他有左儿子，那他的左儿子一定在让父亲辈的右边，所以如果中序往左找左儿子，找到父亲辈了，那就没有左儿子。然后，先构造左节点之后，再找右节点，如果有右儿子，那么 找右儿子的左儿子，然后右儿子，如果找到儿子了，直接找儿子的左儿子，左儿子优先级是最高的。这样，递归的雏形就出现了。

一开始，我用了两个变量一个now，一个now2，now用来记录节点在中序数组的位置，now2用来继续now的父亲在中序的位置，想用来限制查找范围，后来发现，不行。当父亲在儿子右边时，儿子会一直往左找，找到爷爷也不停下来，因为如果有左儿子的话，左儿子的位置一定在他父亲以上辈数的右边，右边查找也有这种情况。所以就取消了now2，使用了在前序中查找有没有父辈来替代。