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

Question

假设你有两棵二叉树，你想知道一棵是否是另一棵的子树。一种解决方案是获取两棵树的中序和前序遍历，并检查候选子树的遍历是否是另一棵树相应遍历的子串。我阅读了几篇关于此解决方案的帖子。一discussion表明中序和前序遍历都是必要的。有人可以解释为什么它们就足够了吗？为什么如果 tree2 的中序和前序遍历是 tree1 的子串，那么 tree2 是 tree1 的子树？

Answer 1

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 是树的根。从中序可以确定左右子树，从这里开始递归:

                 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 .由于组合在一起的树的这两个序列化(遍历实际上将树序列化为字符串)对于二叉树来说必须是唯一的，因此当且仅当这些遍历是其他两个序列化的子串时，我们得到一棵树是另一棵树的子树。