java - 如何从二叉树的中序值和后序值重新创建二叉树？

Question

Inorder: 3 2 1 5 4 6 8 9 7 11 10
Postorder: 1 2 3 4 5 6 9 11 10 7 8

我相信我走在正确的轨道上，将最后一个后序值作为根，在 Inorder 列表中找到该值并将树拆分到该值的左侧和右侧。从我一直在尝试的情况来看，我能够得出这个结果：它的格式不正确，所以我截图了。

Answer 1

从 Postorder 中获取最后一个元素，这是您的根元素，然后在 Inorder 中找到该元素并在左右列表中拆分元素，给您 LEFT：“3 2 1 5 4 6”和 RIGHT：“9 7 11 10 " 然后遍历 Postorder 列表并在找到 Inorder 列表中根元素索引之前的第一个数字后将其拆分，在这种情况下，这是“6”，所以一直走到 6，这将为您提供“1 2 3 4 5 6”，其余为“9 11 10 7”。然后以相反的顺序插入这些列表，例如：“6 5 4 3 2 1”，然后是“7 10 11 9”，这应该会给你正确的树顺序。

Answer 2

这有点棘手，也许是因为与大脑半球有点矛盾；-)

感兴趣的参数是：

• post: 包含后序遍历的数组
• lp:post数组的左索引
• rp:post数组的右索引
• in: 包含中序遍历的数组
• li:in数组的左索引
• ri:ìn数组的正确索引

该过程是“自然”递归的。在每次递归时，根始终是post[rp]。那是最后访问的节点（按后序）。

所以，首先要做的是知道数组中根的索引in。为了计算它，我们从lito扫描ri并搜索post[rp]。让i根在数组中的索引in。我假设树没有重复的键。

给定根的索引，那么

1. i - li是左子树中的节点数
2. ri - i是右子树中的节点数

现在，in变得自然分区。左子树介于 之间[li, i - 1]，右子树介于 之间[i + 1, ri]。

我认为有点困惑的是确定子树在post. 左子树介于 之间[lp, lp + (i - li) - 1]，右子树介于 之间[rp - (ri - i), rp - 1]。考虑上面表达的每个子树的节点数（在枚举列表中）。

有了这些知识，我们就可以设计算法了（我用伪 C++ 编写，但我认为它很容易翻译成 java）：

Node * build_postorder(const vector<int> & post, long lp, long rp,
                       const vector<int> & in, long li, long ri)
{
  if (lp > rp)
    return nullptr; // we stop recursion when the tree is empty

  Node * root = new Node(post[rp]); // Creates the root with key value post[rp]

  int i = li;
  for (; i <= ri; ++i) // search in inorder array the index of root
    if (in[i] == post[rp])
      break; // this line must always to execute it (if everything is oK)

  LLINK(root) = build_postorder(post, lp, lp + (i - li) - 1, in, li, i - 1);
  RLINK(root) = build_postorder(post, rp - (ri - i), rp - 1, in, i + 1, ri);

  return root;
}

祝你好运！