我们可以构造一个只有后序遍历或前序遍历的完整二叉树吗？

Question

例如,我们只提供post order遍历数组或只提供pre order遍历数组.我们可以重新构建二叉树吗？如果我们知道二叉树已满.而且,如果不是,如果同时知道预订单和后期订单,是否可以构造完整的二进制文件？

Answer 1

不,你不能单独列出一个清单.

想一下后序清单: 4 5 2 3 1

    1         1   
   / \       / \
  2   3     4   3
 / \           / \
4   5         5   2

两棵树都是可能的,但我们不知道哪一个生成了列表

假设树中的每个元素都是唯一的,我们知道preorder是这样构建的:

[Node][     LeftTree     ][     RightTree     ]

和这样的后序:

[     LeftTree     ][     RightTree     ][Node]

如果我们有两个列表,预订单1 2 4 5 3和后序4 5 2 3 1,我们知道这1是树的根,因为它是预订单列表的第一个数字(以及后序列表的最后一个数字).此外,我们知道2必须是左树3的根和右树的根,因为它们是根节点之后的第一个数字,它们是左或右树的根.考虑到这一点,我们可以将列表拆分为:

           [Root in preorder] [ LeftTree ] [RightTree] [Root in postorder]
preorder:        [1]             [2 4 5]      [3]     
postorder:                       [4 5 2]      [3]              [1]   

从这里你可以用左右树递归地做这个算法,最后得到这个:

    1     
   / \      
  2   3    
 / \       
4   5

由于每个元素都是唯一的,因此只有一种方法可以构建树,因此您可以从其后序和预订单列表中重建树.

如果您的元素相同,则无法构建唯一的树,例如:

preorder:  1 X X 5 X
postorder: X 5 X X 1

从这些列表中,您可以创建这两个树:

    1         1   
   / \       / \
  X   X     X   X
 / \           / \
X   5         5   X