数据结构基础：根据先序、中序遍历结果构造二叉树

由先序遍历，我们可以确定树根。在上例中，3是先序遍历的第一个结果，所以3肯定是树根；然后再中序遍历的结果中找到3，在3的左边的肯定是根的左子树，在3的右边的肯定是根的右子树。

这样我们就将中序遍历的结果分成三个部分，3的左边（左子树）、3（根）、3的右边（右子树），然后对左右递归处理，递归的结果返回左右子树的根，然后根结点连接左右节点的根就得到结果了。

大致的思路有了，接下来我们深入细节。当我们向左右递归的时候，怎么知道左右子树的根呢？还是要回到先序遍历，我们已经知道左子树和右子树了，我们根据先序遍历的特点——在前面的结果在树中的位置肯定是靠左的——也就是说左子树的先序遍历结果肯定在右子树先序遍历结果的前面。

通过上面的分析，我们的思路就清楚的了，构造步骤如下：

1. 取出先序遍历的结果中未使用的第一个节点作为根
2. 在中序遍历的结果中查找上一步得到的根，然后以改根为支点，将中序遍历的结果分成左右两部分，分别对应左子树和右子树
3. 用上一步得到的结果，将先序遍历的结果分成左右两部分，具体操作是：得到上一步左边部分的长度，在先序遍历的结果中截取相同的长度——左子树的先序遍历结果，然后右边做相同的操作
4. 将左右递归处理，回到第一步

以上面的例子来执行该算法：

1. 拿先序遍历的第一个结果，得到根：3
2. 在中序遍历的结果中搜索3，将中序遍历的结果：[9,3,15,20,7]，分成左右两个部分：[9]，[15,20,7]
3. 将先序遍历的结果：[3,9,20,15,7]，也分成左右两个部分（不包括3了，已经处理过的就不再处理）：[9]，[20,15,7]。现在我们得到的结果看起来向下面这样：

   3
     / \
    9   20,15,7
   复制代码

4. 然后我们对左右分别递归，先拿到左递归的根——取先序遍历中的左边的结果：[9]中的第一个节点9，所有左子树的根就是9，处理中序遍历的左边结果：[9]，发现只有一个节点，直接返回该节点。
5. 然后递归右子树，先拿到右递归的根——取先序比阿尼中有边的结果：[20,15,7]中的第一个节点20，所有右子树的根就是20，现在得到的结果看起来向下面这样：

   3
    / \
   9   20
       |
     15，7 (15，7是20的左右子树，但是现在还不确定谁是左谁是右，需要下一步来确定)
   复制代码

6. 回到第二步，在中序遍历的结果中搜索20，得到左右子树[15]、[7]，此时我们就得到了完整的二叉树：

   3
    / \
   9   20
      /  \
     15   7
   复制代码

javascript代码实现

看到这里应该完整的理解了构造过程了吧～接下来上代码，使用javascript：

/**
* preleft，preright是preorder的左右边界，left和right是inorder的左右边界，因为左右子树在两个遍历结果中的位置不同，所以要区分
*/
function construct(preorderResult,inorderResult,preleft,preright,left,right) {
  if(right-left <= 1) return {
    val: preorderResult[preleft],
    left: null,
    right: null
  }
  // 取根结点
  var troot = preorderResult[preleft];
  // 找到根结点在中序遍历结果中的位置
  var trootIndexInorder = inorderResult.indexOf(troot);
  var lchild=null,rchild=null;
  // 确定左子树的节点数量
  var llength = trootIndexInorder-left;
  // 确定先序遍历结果中左右子树的边界
  var tpreright = preleft+1+llength;
  // 下面的两个if处理边界条件，至少有一个节点时才递归处理
  if(trootIndexInorder > left) {
    lchild = construct(preorderResult,inorderResult,preleft+1,tpreright,left,trootIndexInorder);
  }
  if(trootIndexInorder+1 < right) {
    rchild = construct(preorderResult,inorderResult,tpreright,preorderResult.length,trootIndexInorder+1,right);
  }
  // 返回根结点和左右子树
  return {
    val: troot,
    left: lchild,
    right: rchild
  }
}
复制代码

扩展思考

那现在假如已知中序遍历和后续遍历的结果，要构造二叉树怎么办呢？是不是也可以用类似的思路解决这个问题呢呢？其实思路和前面的是一样，只是要结合后序遍历的特点（与前序相反，根结点在结果的最后面），我这里就只给代码了，如果前面的理解了，这个so easy了。 javascript:

function construct(inorder, postorder, inleft,inright,postleft,postright) {
  if(inright - inleft <= 1) {
    return {
      val: postorder[postright-1],
      left: null,
      right: null
    }
  }
  var troot = postorder[postright-1];
  var trootInorderIndex = inorder.indexOf(troot);
  var lchild = null, rchild = null;
  var rlength = inright-1-trootInorderIndex;
  var tpostright = postright-1-rlength;
  if(trootInorderIndex > inleft) {
    lchild = construct(inorder,postorder,inleft,trootInorderIndex,0,tpostright)
  }
  if(trootInorderIndex+1 < inright) {
    rchild = construct(inorder,postorder,trootInorderIndex+1,inright,tpostright,postright-1);
  }
  return {
    val: troot,
    left: lchild,
    right: rchild
  }
}
复制代码