algorithm - 使用给定遍历验证二叉树

Question

是否有可能在给定两次遍历(例如:顺序遍历和后序遍历)的情况下识别不存在二叉树的序列？

我理解后序遍历的最后一个元素，或前序遍历的第一个元素，是树的根。使用这样的基本事实，是否可以在不实际构建树的情况下测试这些数组并确定它们是否生成相同的树？

我已经有一个算法可以从这两个序列(in- 和 post-)构建树，但如果有一种方法可以预先测试数组，我不想运行该算法。这将节省大量时间，而不是运行算法并在最后找出答案。

注意:这不一定是二叉搜索树。二叉树就足够了。

Answer 1

我重新开始，因为这个问题与我想的有点不同。给定一个中序和后序遍历，你能找到是否有一棵树可以同时生成它们吗？

让我们考虑一下这棵树:

     a
   /   \
  b     e
 / \   / \
c   d f   g

遍历是:

inorder:    CBDAFEG
postorder:  CDBFGEA

现在一些观察:

一个。后序中的最后一个节点始终是根节点。

b 如果您知道根节点，则可以将中序遍历拆分为左遍历、根节点和右遍历。

因此，您可以在不创建树的情况下运行递归算法，以确定它们是否可以由同一棵树生成。

像这样:

给定 Io 和 Po 作为两个遍历，

如果它们的长度不同，则没有共同的树。

如果长度相同则:

1. 取 Po 的最后一个节点 - 称之为 R
2. 在 Io 中找到 R。如果找不到，则没有共同的树。

3. R决定了左右子树的边界，所以根据R在Io中的位置拆分Io和Po:

   CBD A FEG

   CDB FEG A

(例如，一旦你知道左子树必须有 3 个节点长，而右​​ sig 树也有 3 个节点长，你也可以用同样的方式拆分 Po)

1. 在左右子树上递归调用此算法。