证明一棵二叉树是另一棵的子树

Question

假设你有两棵二叉树，你想知道它是否是另一棵的一棵子树。一种解决方案是获取两棵树的顺序和前序遍历，并检查候选子树的遍历是否是另一棵树的相应遍历的子串。我阅读了几篇关于这个解决方案的文章。其中一个discussion显示顺序和前序遍历都是必需的。有人可以解释他们为什么足够吗？为什么如果tree2的inorder和preorder遍历是那些tree1的子串，那么tree2是tree1的一个子树？

Answer 1

问：一个讨论表明，中序和序遍历都是 必要的。有人可以解释他们为什么足够吗？

由于简单的事实，所以能够唯一地重建从这两个遍历的二进制树的（或序和后序，以及）。检查这个例子：

Inorder : [1,2,3,4,5,6] 
    Preorder : [4,2,1,3,5,6] 

从前序，你知道4是树的根。从序，你能确定左，右子树，你从这个角度出发递归：

    4 
      / \ 
    Left subtree  Right subtree 
    Inorder : [1,2,3] Inorder : [5,6] 
    Preorder: [2,1,3] Preorder: [5,6] 

检查这个优秀的文章中更多的细节： Reconstructing binary trees from tree traversal。由于这两个结合在一起的树的串行化（实际上将树序列化为一个字符串）必须是二叉树唯一的，所以当且仅当这些遍历是其他两个串行化的子串时，我们才能得到这棵树是另一棵树的子树。

Answer 2

人们同意二叉树可以通过左/右关系表示节点上的顺序。这意味着左边部分在右边部分之前。如果订单相同，您可以调用相同的树木。所以顺序串表示顺序，如果你想检查等价性，那么仅检查顺序（按定义）就足够了。 但是，当你想检查树的完全平等时，我们必须找到如何区分等价树的方式。例如，它可以是水平顺序检查。但是对于子树级别的顺序不适合，因为子树的级别顺序字符串被拆分。对于预购，您可以在树的其他部分之前行走子树树根。

假设等价树不相等，那么在预先遍历中，所有东西都是相等的，直到第一个不同。 2种情况可能发生。

1）一棵树的节点值不同。这意味着预购字符串不同，因为您按预订顺序走树。

2）孩子签名（没有孩子，只有左边，只有右边，两个孩子）不同。但在这种情况下，易于理解的是有序变化和树木不等价，这与条件相矛盾。

请注意，这仅适用于所有节点都是唯一的。如果你的所有节点的价值都是“a”，那么无论你如何走路，你的字符串总是“aa ... a”。所以你必须以某种方式区分节点，而不仅仅是“价值”。