中序遍历、前序遍历和后序遍历在处理空元素时的独特性

Question

我们都知道不同的二叉树可能拥有相同的中序遍历、先序遍历或后序遍历。但是如果我们在先序遍历中包含null元素，那么只要这些树是唯一的，遍历结果就会是唯一的。考虑下面这两棵树：

  3                      3
 /                        \
4            vs.           4

他们正常的 前序遍历 对于两者来说都是 {3,4}，但如果我们包括 null 元素，那么它们的遍历分别将是 {3,4,null,null,null} 和 {3,null,4,null,null}，使得遍历变得独特。

我的问题是，对于中序遍历和后序遍历也是这样吗？我们如何证明呢？

- bli00

Answer 1

对于后序遍历来说，这是正确的，因为它只是翻转树的前序遍历。

对于中序遍历来说，这并不正确，因为它总是以 null 开始、以 null 结尾，并且在 null 和节点之间交替。

例如，这些树：

  B          D    
 / \        / \
A   D      B   E
   / \    / \
  C   E  A   C

两者都产生

null, A, null, B, null, C, null, D, null, E, null

- Matt Timmermans

---

能否有一个正式的令人信服的证明呢？ - Rohit Singh

很容易从叶子归纳得出，但没有充分的理由去这样做。任何被这种证明说服的人，却不被这个演示所说服的人，只是在寻找长词和听起来聪明的语言。 - Matt Timmermans

同意你的观点。但是这种证明通常在理论考试中是必需的。这就是我对它们感兴趣的原因。 - Rohit Singh

Answer 2

中序遍历不正确。
例如：

      2                     2
     / \                   / \
    2   n                 n   2
   / \                       / \
  n   n                     n   n

它们都是 [n, 2, n, 2, n]

前序遍历和后序遍历是正确的，因为有两个空节点，我们可以确定一个父节点，而这个父节点必须是其他节点的子节点，以此类推。我们总是可以确定一个唯一的父节点。但对于中序遍历来说，情况并非如此。

- Wenlong Feng