这道题目是根据前序和中序遍历，构造一棵二叉树。数据结构里面的，但是做的时候还是没有头绪，因为有一个我的软肋（我全身没有什么硬肋骨）：递归。但是还是硬着头皮，分析了一下，最后总算做出来了，但是结果却并不满意：慢的要死内存还很大…。想着先整理一下思路，然后看看别人的代码有什么特别之处。
先说一下思路，抛开编程，根据两个序列构造一个二叉树在数据结构中会出现这种题目，基本上就是在前序遍历中找根，在中序遍历中找左右子树。这样，思路就简单了，其实编程也是这样，先在前序遍历中找到根节点，然后找到这个根节点对应的左右子树，最后递归构造左右子树。说实话，如期说是递归构造左右子树，在程序上体现出来的话，更明显的说法是找左右子树的根节点，然后继续向下找。找到最后叶子节点作为根节点时，就没有下面的根节点了。
感觉自己嘴笨，还是直接上程序吧：
public TreeNode buildTree(int[] preorder, int[] inorder) {
return helper(0, 0, inorder.length - 1, preorder, inorder);
}public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
if (preStart > preorder.length - 1 || inStart > inEnd) {
return null;}TreeNode root = new TreeNode(preorder[preStart]); //1. 先构造这个树的根节点int inIndex = 0; // Index of current root in inorder //2. 找到根节点在中序遍历中的下标for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == root.val) {
inIndex = i;}} root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder); //3.1 有了所有下标，就可以构造出它的左子树//3.2 有了所有下标，就可以构造出它的右子树root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);return root;
}
程序说明一下：如果我们想构造一棵二叉树，要有它的前序和中序遍历序列，所以原理一样，如果我们要构造左右子树的时候，也要知道左右子树所对应的前序和中序遍历序列。所以先看函数helper的参数：有一个preStart就是某一个树在前序中的开始下标；instart就是某一个树在中序遍历中开始的下标；inEnd则是在中序遍历中结束的下标。那我们有了这三个下标怎么做呢，我们先在前序中找到某一个树的根节点，然后找到它在中序遍历中的下标。当我们有了这个下标，就能知道左子树的长度是多少、右子树的长度是多少（通过inIndex、inStart、inEnd）；同时能知道左子树和右子树所对应的中序遍历的下标（同样是通过inIndex、inStart、inEnd）、所对应的前序遍历的下标（通过preStart和刚才计算出来的两个长度），都得出来以后我们就又能构造一个左子树和一个右子树，然后将构造出来的树赋给root.left和root.right，就搞定了。
当然最后肯定是有一个结束的，也就是helper的第一个判断语句，那到底什么时候会结束呢？首先先看后面那个判断条件inStart > inEnd，这个比较容易理解，如果成立说明这个树中序遍历的长度小于0，即不存在了，所以返回Null；前面那个preStart > preorder.length - 1呢，其实它就是表示已经遍历到头了。即先序遍历开始已经超出整个数组范围，所以这个树的根节点超出范围，也就是没有。这样就是两个条件保证结束：
preStart > preorder.length - 1保证这个树的根节点对应下标不会超过数组长度-1，这样这个树的根节点就一定存在，否则返回null。inStart > inEnd保证这个树长度大于0，否则这个树就是空的，返回null。
#######################################
所以总结一下看也不难，其实就是找到一个树在前序和中序中的下标，然后就是找根节点，再更新左右子树对应在两个遍历序列中的下标，继续更新。结束条件一个是针对树的根节点要存在，一个是针对树的长度要大于0.
2020.3.8 妇女节快乐…
在复习剑指offer时，又重新使用树的长度作为终止条件来做了一次，终止条件也没有那么麻烦了。首先我们知道当前树的根节点时前序遍历的开始节点in[inStart]，我们找到它在中序遍历的位置，然后此时我们知道的信息有：
- 当前树的根节点
in[rootIndex]或者pre[preStart] - 左子树前序遍历序列的开始下标：
inStart+1，中序遍历序列的开始下标：inStart - 左子树的长度：
rootIndex-inStart - 右子树前序遍历序列的开始下标：
inStart+rootIndex-inStart+1，即左边根节点加上左子树长度再加上根节点长度后；中序遍历序列的开始下标：rootIndex+1 - 右子树的长度：
length-1-(rootIndex-inStart)，即总长度-根节点-左子树长度
这样我们就可以递归构造下一层了，当树的长度为0时，返回null
public class Solution {
public TreeNode reConstructBinaryTree(int[] pre,int[] in) {
return helper(pre, in, 0, 0, pre.length);}/*** @param preStart: 前序遍历的开始下标* @param inStart: 中序遍历的开始下标* @param length: 当前树的长度* @return 当前树的根节点*/private TreeNode helper(int[] pre, int[] in, int preStart, int inStart, int length) {
if (length == 0) //树的长度为0，直接返回return null;int rootIndex = inStart; //找到中序遍历的根for (int i = 0; i < length; ++i) {
if(in[inStart+i] == pre[preStart]) {
rootIndex = inStart+i;break;}}TreeNode root = new TreeNode(in[rootIndex]);root.left = helper(pre, in, preStart+1, inStart, rootIndex-inStart);root.right = helper(pre, in, preStart+rootIndex-inStart+1, rootIndex+1, length-rootIndex+inStart-1);return root; //最后返回当前树的根节点}
}