我们都知道不同的二叉树可以有相同的中序、前序或后序遍历。但是如果我们要将 null 元素包含到 preorder 遍历中，那么只要树是唯一的，遍历的结果就是唯一的。考虑这两棵树:
3 3
/ \
4 vs. 4
他们正常的 preorder 遍历对于两者都是 {3,4}，但是如果我们要包含 null 元素，那么他们的遍历将分别为 {3,4,null,null,null} 和 {3,null,4,null,null}，使遍历唯一。
我的问题是，中序遍历和后序遍历是否也是如此？我们如何证明这一点？
最佳答案
对于后序遍历来说是正确的，因为这只是倒序树的前序遍历的逆。
中序遍历不是这样，它总是以 null 开始，以 null 结束，并在 null 和节点之间交替。
例如，这些树:
B D
/ \ / \
A D B E
/ \ / \
C E A C
都生产
null, A, null, B, null, C, null, D, null, E, null
关于algorithm - 具有空元素的中序、先序和后序遍历的唯一性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45871284/