algorithm - 我们能否构造一棵只有后序遍历或前序遍历的满二叉树？

Question

比如我们只提供后序遍历数组或者只提供前序遍历数组。我们可以重建二叉树吗？如果我们知道二叉树是满的。此外，如果不是，如果同时知道前序和后序，是否可以构造完整的二进制文件？

Answer 1

不，您不能仅从一个列表中选择。

想想后序列表:4 5 2 3 1

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

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

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

[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