- 二叉树拼图 - 从这些遍历中绘制树：

Question

顺序：S A E U Y Q R P D F K L M

预购：F A S Q Y E U P R D K L M

我很困惑如何处理中间部分。似乎没有任何组合有效，帮助？有人有技巧吗？我该如何处理？我已经为此苦苦思索了 2 个小时。

我必须恢复这棵树。

Answer 1

正确的结果是

我将尝试为您提供一般性解释，而不是为您的示例提供具体解释。我认为它更有用，毕竟你可以用你的具体案例测试算法，看看算法是否有效并更好地理解。

你可以用递归的方式思考这个问题。

为了方便解决问题，我们可以就一些变量达成一致

preorder：包含前序遍历的数组
inorder：包含中序遍历的数组
l_p: preorder 数组中的左索引
r_p: preorder 数组中的右索引
l_i: inorder 数组中的左索引
r_i: inorder 数组中的右索引

在您的具体示例中，第一个实例是 l_p = l_i = 0 和 r_p = r_i = 12。

这样可以方便解释：

index     0 1 2 3 4 5 6 7 8 9 10 11 12
preorder: F A S Q Y E U P R D  K  L  M
inorder:  S A E U Y Q R P D F  K  L  M
          <      left     > ^   < right >
                            |
                      this is the root

一个非常重要的事实是要认识到当前树的根总是preorder[l_p]，第一次是F。现在，您必须识别树的左右分支，它们在 inorder 数组中清楚地区分（见上图）。为了知道这一点，您在 inorder 数组中搜索包含根 F 的索引；这个索引是 9。我们可以看到根在l_i之后的九处。设 i 一个变量，表示相对于 l_i 有多少位置是树的根。

所以，左树的键在inorder数组中0和8之间，右树的键在10和[=之间37=]。

为了递归构建左树你有l_p = l_p + 1，因为你已经看到了根，还有r_ p = l_p + i =，但是数组inorder被[=41分隔=] 和 r_i = l_i + i - 1 =8.

同理，右树在preorder在l_p = l_p + i + 1 = 10和r_p = r_p = 12之间，而在数组inorder中是在l_i = l_i + i + 1之间和 r_i.

有了所有这些（有点复杂）我们可以勾勒出一个算法：

Node * build_tree(int preorder[], int l_p, int r_p,
                  int inorder[], int l_i, int r_i)
{
  if (l_p > r_p)
    return nullptr; // empty tree

  Node * root = new Node;
  root->key = preorder[l_p];

  int i = 0; // now we search index of preorder[l_p] in inorder array
  for (int j = l_i; j <= r_i; ++j)
    if (inorder[j] == preorder[l_p])
      {
        i = j - l_i; // the root is at l_i + i
        break; // always breaks if everything is ok
      }

  root->left = build_tree(preorder, l_p + 1, l_p + i, 
                          inorder, l_i, l_i + (i - 1));
  root->right = build_tree(preorder, l_p + i + 1, r_p, 
                           inorder, l_i + i + 1, r_i);
  return root;
}

- 二叉树拼图 - 从这些遍历中绘制树：

- Binary Tree Puzzle - Draw tree from these traversals:

tree

binary-tree

inorder

preorder