具有空元素的有序，预订货和后订货遍历的唯一性

Question

我们都知道不同的二叉树可以具有相同的inorder，preorder或postorder遍历。但是，如果我们将null元素包括在预定遍历中，则遍历的结果将是唯一的，只要树是唯一的即可。考虑以下两棵树：

  3                      3
 /                        \
4            vs.           4

它们的正常预遍历将同时{3,4}用于两者，但是如果我们要包含null元素，则它们的遍历将是{3,4,null,null,null}和{3,null,4,null,null}尊敬，使穿越独特。

我的问题是，对于有序遍历和后序遍历也是如此吗？我们怎么证明呢？

Answer 1

Mat*_*ans 6

对于后序遍历是正确的，因为那只是反向树的前序遍历的逆过程。

对于有序遍历并不是正确的，遍历遍历总是以null开始，以null结尾，并在null和节点之间交替。

例如，这些树：

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

都产生

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