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

Question

订购：SAEUYQRPDFKLM

预购：FASQYEUPRDKLM

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

我必须恢复这棵树。

Answer 1

正确的结果是

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

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

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

• preorder: 包含前序遍历的数组
• inorder: 包含中序遍历的数组
• l_ppreorder:数组中的左索引
• r_ppreorder:数组中的右索引
• l_iinorder:数组中的左索引
• r_iinorder:数组中的右索引

在您的具体示例中，第一个实例是l_p = l_i = 0and 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数组中搜索包含 root 的索引F；这个指数是9。我们可以看到根在 之后的九个位置l_i。让i一个变量表示相对于多少个位置l_i是树的根。

所以，左树的键在和inorder之间，右树的键在和之间。081012

为了递归地构建你有的左树l_p = l_p + 1，因为你已经看到了根，and r_ p = l_p + i =，但是数组inorder由l_i = 0and分隔r_i = l_i + i - 1 =8。

同理，右树在andpreorder之间，而在数组中它在and之间。l_p = l_p + i + 1 = 10r_p = r_p = 12inorderl_i = l_i + i + 1r_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;
}