题目大意：
从前序与中序遍历序列构造二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素
例如，给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7 如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=105
解题思路分析：
这是一道经典题目，首先我们需要充分理解前序遍历以及中序遍历的概念，简单来说，前序遍历是根节点->左子树->右子树的顺序打印节点。而中序遍历则是从二叉树的最左列开始向右逐列打印，严格来讲，二叉树中的每个节点都不在同一列上，换句话说，每一列实际上只存在一个节点，因为对于任何一个节点，他的左子树上的节点都在其左侧，右子树上的节点都在其右侧，所以，是不存在多个节点在同列的情况的。（对于二叉搜索树bst来说，中序遍历的结果实际上就是将所有节点按照升序排列后的结果。）
对于本题，题目给出了前序遍历以及中序遍历后的打印结果。根据上文，前序遍历是从根节点开始打印，所以preorder[0]一定是二叉树的根节点root。另外，该根节点也一定存在于中序遍历的数组中，我们通过循环中序数组能够轻松找到该root值所在的位置i，在中序遍历数组inorder中，inorder[0]至inorder[i-1]的部分一定是根节点root左子树的中序遍历，而inorder[i+1]至inorder[length-1]则是根节点右侧的中序遍历。我们分别求出左右两侧中序遍历子数组长度，定义为L和R。
这时，我们将中序数组拆分为root节点，左子树中序遍历子数组和右子树中序遍历子数组三个部分，接下来考虑，对应根节点左子树中序遍历子数组在前序遍历数组中的位置（有些绕口，具体可参照下方例子），毫无疑问，应该是 preorder [1]至preorder [1+L-1](从preorder下标为1处向后数L个元素) ，同理， 对应根节点右子树中序遍历子数组在前序遍历数组中的位置应该是preorder [1+L]至数组结尾部分。这样我们也将前序数组拆分为了三部分。我们新建一个节点对象，将根节点root的值赋予该节点，根节点的左子节点可以在左子树的前序子数组和中序子数组中找到（递归）， 根节点的右子节点可以在右子树的前序子数组和中序子数组中找到（递归）。
我们举例来说明，比如题目给出的例题：
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]
首先，前序遍历的首元素3一定是二叉树的根节点。这时我们再来看3在中序遍历中的位置是下标1，对于中序遍历数组，3的左边一定是它的左子树所有节点，同理它的右边一定是它的右子树所有节点，也就是说根节点3的左子树有1个节点，而右子树有3个节点。因此，我们可以将中序遍历数组inorder分解为三个部分：
[9] [3] [15,20,7] 左子树 根节点 右子树
既然中序遍历数组可以分为三部分，那么前序遍历数组同样可以分为三部分，我们已知前序遍历的首元素是根节点，那么左子树所在的位置一定是首元素后紧邻的几个数字组成的子数组，该子数组长度也一定会等于中序遍历数组中左子树的长度。而剩下的部分也就对应了中序数组的右子树部分。
[3] [9] [20,15,7] 根节点 左子树 右子树
我们将两个数组放在一起比较一下：
// 中序数组 [9] [3] [15,20,7] 左子树 根节点 右子树 // 前序数组 [3] [9] [20,15,7] 根节点 左子树 右子树
找到了根节点和左右子树后，我们首先构建一个根节点出来，而他的右子树可以递归至子问题去解决，该子问题可以理解为：中序数组为[15,20,7]，前序数组为[20,15,7]，求该二叉树。子问题的解题思路与当前问题完全一致。我们将子问题的返回值设置为当前节点的右子节点即可。另外，左子节点也同理可得。递归的终止条件为当前数组长度为1时，返回当前节点即可。
实现代码：
public TreeNode buildTree(int[] preorder, int[] inorder) {
return help(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
}
// preorder 前序数组
// inorder 中序数组
// lp 前序数组范围起点
// rp 前序数组范围终点
// li 中序数组范围起点
// ri 中序数组范围终点
TreeNode help(int[] preorder, int[] inorder, int lp, int rp, int li, int ri){
// 如果是非法范围，返回空
if(lp>rp||li>ri) return null;
// 前序数组范围起点为当前根节点
int rootVal = preorder[lp];
// 新建根节点对象
TreeNode root = new TreeNode(rootVal);
// 在中序遍历数组范围内找到该根节点的位置
for(int i=li;i<=ri;i++){
// 如果当前值等于根节点
if(inorder[i]==rootVal){
// 递归查找左子节点
root.left=help(preorder,inorder,lp+1,lp+(i-li),li,i-1);
// 递归查找右子节点
root.right=help(preorder,inorder,lp+(i-li)+1,rp,i+1,ri);
break;
}
}
return root;
} 本题解法执行时间为3ms。
Runtime: 3 ms, faster than 57.34% of Java online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
Memory Usage: 41.5 MB, less than 10.28% of Java online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-105-construct-binary-tree-from-preorder-and-inorder-traversal-解题思路分析/