我正在阅读的一本书声称，检查二叉树是否是二叉树B的子树的一种A方法是构建两棵树的inorder和preorder字符串（表示每棵树的中序和前序遍历的字符串），并检查是否inorder_B是inorder_A 和 的子串preorder_B是 的子串preorder_A。请注意，它声称您必须检查inorder和preorder 字符串的子字符串匹配。
是否真的有必要检查中序和预序字符串上的子字符串匹配？不也来检查一下吗？有人可以提供一个例子来证明我错了（即证明书中的主张是正确的）吗？我想不出两棵树不相等但前序或中序字符串匹配的例子。
考虑以 A 和 B 作为节点的两棵两节点树。树一有 B 作为根，A 作为左孩子。树二以 A 为根，B 为右孩子。中序遍历匹配，但树不同。
如果树不是二叉搜索树而是普通二叉树，我认为你需要两者。任何一组节点都可以是预序符号。假设有一棵二叉树 a,b,c,d,e,f,g,h 并且您的子树是 cdef。您可以使用子树 cde 和另一个子树 fg 创建另一个树。没有办法知道区别。
如果它是二叉搜索树，那么你不需要中序。
顺便说一句，这里有一个有趣的算法问题：给定一个预序符号，找到满足它的二叉树的数量。
作为对user1952500回答的补充：如果是二叉搜索树，则只有前序或只有后序才能使其唯一，而只有中序不能。例如：
5
/ \
3 6
inorder: 3-5-6 然而，另一个二叉搜索树可以有相同的顺序：
3
\
5
\
6
另外，我相信 preorder+inorder+string_comparison 仅用于检查两棵树是否相同。它无法检查一棵树是否是另一棵树的子树。要查看示例，请参阅 使用前序字符串和中序字符串确定二叉树是否是另一棵二叉树的子树
使用哨兵进行前序遍历来表示空节点就足够了。我们可以使用这种方法来序列化/反序列化二叉树。这意味着在二叉树和它的前序之间存在一对一的映射，具有哨兵表示。