证明一棵二叉树是另一棵的子树
Proving that one binary tree is a subtree of another
假设你有两棵二叉树，你想知道一个是否是另一个的子树。一种解决方案是获取两棵树的中序和前序遍历，并检查候选子树的遍历是否是另一棵树相应遍历的子串。我阅读了几篇关于此解决方案的帖子。一个 discussion 表明中序和前序遍历都是必要的。有人可以解释为什么它们就足够了吗？为什么如果 tree2 的中序和前序遍历是 tree1 的子串，那么 tree2 是 tree1 的子树？
人们同意二叉树可以通过 left/right 关系表示其节点上的顺序。这意味着左边的部分在右边的部分之前。如果顺序相同，您可以将树称为等效树。所以 in-order 字符串代表顺序，如果你想检查等价性，那么只检查 in-order （根据定义）就足够了。
但是当你想检查树的完全相等性时，我们必须找到我们如何区分等价物的方法 trees.For 例如它可以是 level-order 检查。但是对于子树级别顺序不适合，因为子树的级别顺序字符串被拆分。对于 pre-order ，您在树的其他部分之前从根走子树。
假设等价树不相等，那么遍历pre-order所有东西都会相等，直到第一个不同。可能会发生 2 种情况。
1) 一棵树的节点值与另一棵不同。这意味着 pre-order 字符串不同，因为您在 pre-order.
中遍历树
2) Children 签名（没有 children，只有左边，只有右边，都有 children）不同。但是在这种情况下容易理解，in-order会发生变化，树不等价，这与条件相矛盾。
请注意，这仅在所有节点都是唯一的情况下才有效。如果你所有节点的值都像 "a" 那么无论你怎么走，你的字符串总是 "aa...a"。所以你必须以某种方式区分节点，而不仅仅是 "value".
Q: One discussion shows that inorder AND preorder traversal are both
necessary. Can someone explain why they are sufficient?
因为一个简单的事实，即可以唯一地从这两个遍历（或中序和后序）重建二叉树。检查这个例子：
Inorder : [1,2,3,4,5,6]
Preorder : [4,2,1,3,5,6]
根据预购，您知道 4 是树的根。从inorder可以确定左右子树，从这里开始递归：
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。由于组合在一起的树的这两个序列化（遍历实际上将树序列化为字符串）对于二叉树来说必须是唯一的，因此当且仅当这些遍历是其他两个序列化的子串时，我们得到一棵树是另一棵树的子树。
假设你有两棵二叉树，你想知道一个是否是另一个的子树。一种解决方案是获取两棵树的中序和前序遍历，并检查候选子树的遍历是否是另一棵树相应遍历的子串。我阅读了几篇关于此解决方案的帖子。一个 discussion 表明中序和前序遍历都是必要的。有人可以解释为什么它们就足够了吗？为什么如果 tree2 的中序和前序遍历是 tree1 的子串，那么 tree2 是 tree1 的子树？
人们同意二叉树可以通过 left/right 关系表示其节点上的顺序。这意味着左边的部分在右边的部分之前。如果顺序相同，您可以将树称为等效树。所以 in-order 字符串代表顺序，如果你想检查等价性，那么只检查 in-order （根据定义）就足够了。 但是当你想检查树的完全相等性时，我们必须找到我们如何区分等价物的方法 trees.For 例如它可以是 level-order 检查。但是对于子树级别顺序不适合，因为子树的级别顺序字符串被拆分。对于 pre-order ，您在树的其他部分之前从根走子树。
假设等价树不相等，那么遍历pre-order所有东西都会相等，直到第一个不同。可能会发生 2 种情况。
1) 一棵树的节点值与另一棵不同。这意味着 pre-order 字符串不同，因为您在 pre-order.
中遍历树2) Children 签名（没有 children，只有左边，只有右边，都有 children）不同。但是在这种情况下容易理解，in-order会发生变化，树不等价，这与条件相矛盾。
请注意，这仅在所有节点都是唯一的情况下才有效。如果你所有节点的值都像 "a" 那么无论你怎么走，你的字符串总是 "aa...a"。所以你必须以某种方式区分节点，而不仅仅是 "value".
Q: One discussion shows that inorder AND preorder traversal are both necessary. Can someone explain why they are sufficient?
因为一个简单的事实，即可以唯一地从这两个遍历（或中序和后序）重建二叉树。检查这个例子：
Inorder : [1,2,3,4,5,6]
Preorder : [4,2,1,3,5,6]
根据预购，您知道 4 是树的根。从inorder可以确定左右子树，从这里开始递归：
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。由于组合在一起的树的这两个序列化（遍历实际上将树序列化为字符串）对于二叉树来说必须是唯一的，因此当且仅当这些遍历是其他两个序列化的子串时，我们得到一棵树是另一棵树的子树。