具有空元素的中序、前序和后序遍历的唯一性

问题描述

我们都知道不同的二叉树可以有相同的inorder、preorder或postorder遍历.但是如果我们将 null 元素包含到 preorder 遍历中，那么只要树是唯一的，遍历的结果就是唯一的.考虑这两棵树:

We all know that different binary trees can have the same inorder, preorder, or postorder traversal. But if we were to include null elements into a preorder traversal, then result of the traversal would be unique as long as the trees are unique. Consider these two trees:

  3                      3
 /                        \
4            vs.           4

它们正常的 preorder 遍历对于两者都是 {3,4}，但是如果我们要包含 null 元素，那么它们的遍历将分别是 {3,4,null,null,null} 和 {3,null,4,null,null} ，使遍历唯一.

Their normal preorder traversal would be {3,4} for both, but if we were to include null elements, then their traversal would be {3,4,null,null,null} and {3,null,4,null,null} respectfully, making the traversal unique.

我的问题是，对于中序遍历和后序遍历也是如此吗?我们如何证明这一点?

推荐答案

对于后序遍历是正确的，因为这只是反向树的前序遍历的逆序.

It is true for a postorder traversal, because that's just the reverse of the preorder traversal of the reversed tree.

对于中序遍历来说不是这样，它总是以空值开始，以空值结束，并在空值和节点之间交替.

It is NOT true for an inorder traversal, which would always start with null, end with null, and alternate between nulls and nodes.

例如，这些树:

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

两者都产生

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

这篇关于具有空元素的中序、前序和后序遍历的唯一性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！