我们可以构造，只有后序遍历或preorder穿越满二叉树？ [英] Can we construct a full binary tree with only postorder traversal or preorder traversal?

问题描述

例如，我们只设有后序遍历数组或只pre序遍历数组。我们可以重建二叉树回来？如果我们知道二叉树已满。此外，如果它不是，它是可以构建完整的二进制文件，如果知道这两个preorder及提交订单在同一时间？

For example, we are provided with only post order traversal array or only pre order traversal array. Can we reconstruct the binary tree back? If we know that the binary tree is full. Moreover, if it is not, is it possible to construct the full binary if know both preorder and post order at the same time?

推荐答案

没有，你不能仅仅从一个列表中。

No, you can't from one list alone.

想后序清单： 4 5 2 3 1

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

这两个目录树是可能的，但我们并不知道哪一个生成的列表

both trees are possible, but we don't know which one generated the list

假设树中的每一个元素都是独一无二的，我们知道，preorder是建立这样的：

Assuming every element in the tree is unique, we know that preorder is build like that:

[Node][     LeftTree     ][     RightTree     ]

和后序是这样的：

[     LeftTree     ][     RightTree     ][Node]

如果我们有两个列表，preorder 1 2 4 5 3 和后序 4 5 2 3 1 我们知道 1 是树的根，因为它是preorder列表中的第一个数字（和后序列表的最后一位数字）。此外，我们知道， 2 必须是左树的根和 3 右树的根，因为他们是根节点之后分别是左或右树的根部的第一号。考虑到这一点，我们可以将列表分割成这样：

if we have two lists, preorder 1 2 4 5 3 and postorder 4 5 2 3 1, we know that 1 is the root of the tree, because it is the first number of the preorder list (and the last number of the postorder list). Furthermore we know that 2 must be the root of the left tree and 3 the root of the right tree, because they are the first numbers after the root node which are roots of the left or right tree. With this in mind we can split the lists into this:

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

在这里，您可以递归执行这个算法与左，右树，并最终你会得到这样的：

From here you can do this algorithm recursively with the left and right tree and in the end you get this:

    1     
   / \      
  2   3    
 / \       
4   5

由于每一个元素都是独一无二的，只有一个建在树的方式，因此，你可以从它的后序和preorder列表重建一棵树。

Since every element is unique there is only one way to build the tree and therefore you can rebuild a tree from its postorder and preorder list.

如果您有这都是一样的，你不能建立一个独特的树，例如元素：

In case you have elements that are the same you can't build a unique tree, example:

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

从这些列表，你可以创建这两个树：

from these lists you could create these two trees:

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

这篇关于我们可以构造，只有后序遍历或preorder穿越满二叉树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！