假设你有两棵二叉树，你想知道一棵是否是另一棵的子树。一种解决方案是获取两棵树的中序和前序遍历，并检查候选子树的遍历是否是另一棵树相应遍历的子串。我阅读了几篇关于此解决方案的帖子。一discussion表明中序和前序遍历都是必要的。有人可以解释为什么它们就足够了吗？为什么如果 tree2 的中序和前序遍历是 tree1 的子串，那么 tree2 是 tree1 的子树？
最佳答案
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 .由于组合在一起的树的这两个序列化(遍历实际上将树序列化为字符串)对于二叉树来说必须是唯一的，因此当且仅当这些遍历是其他两个序列化的子串时，我们得到一棵树是另一棵树的子树。
关于algorithm - 证明一棵二叉树是另一棵的子树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32729428/