树遍历问题 - 教科书问题

Question

这是一个教科书中的问题，其中提供了有关二进制树的答案。

如果邮政遍历访问二进制树的节点，以u，g，t，r，a，i的顺序存储字符值，则访问顺序是同一二进制树的遍布遍历的访问顺序？

a）i，g，u，a，a，t，r

b）r，g，u，i，i，t，a

c）g，u，i，i，t，a，r

d）无法确定

答案：c

---

现在问题是答案的方式。我意识到，仅靠邮政遍历不足以唯一地iD树，并且可以为任何类型的树（不订购）定义前订单和后订单遍历遍历，但不能将树一起唯一地iD。内存和邮政遍历可以。这个问题并未指定BST，因此可以有所作为。因此，我想我需要澄清答案是c而不是d的，这就是我认为的。

Answer 1

我同意你的评价。

尽管选项 C 确实与给定的后序遍历兼容——当我们采用这棵树时：

   I                Inorder: G U I T A R
 /   \              Postorder: U G T R A I
G     A
 \   / \
  U T   R

...选项 A 也与给定的后序遍历兼容，如果我们采用这棵树：

    I               Inorder: I G U A T R
     \              Postorder: U G T R A I
      A
    /   \
   G     R
    \   /
     U T

正如您正确指出的那样，单独的后序遍历并不能唯一地定义二叉树，唯一正确的答案是无法确定中序遍历（选项D）。

除非原来的问题有额外的信息，否则这是一个坏问题。