使用先序遍历和中序遍历字符串检查子树

Question

我正在阅读的一本书声称，检查二叉树 B 是否是二叉树 A 的子树的一种方法是构建两个树的 inorder 和 preorder 字符串（表示每个树的中序遍历和前序遍历的字符串），并检查 inorder_B 是否是 inorder_A 的子字符串 以及 preorder_B 是否是 preorder_A 的子字符串。请注意，它声称您必须在中序和前序字符串上都检查子字符串匹配。

真的有必要在中序和前序字符串上都检查子字符串匹配吗？检查任意一个不就足够了吗？有人能提供一个例子来证明我错了吗（即证明书中的说法正确）？我找不到一个两棵树不等但前序或中序字符串匹配的例子。

- fo_x86

---

只做层序遍历怎么样？这只需要一次遍历而不是两次。我并不是要忽视这个问题，只是以防你只是在寻找可行的遍历方法。 - kasavbere

谢谢您的建议。事实上，下一节将介绍使用层序遍历更高效的算法。这样可以避免构建先序/中序字符串，因为随着树的大小增长，这种方法并不太可行。 - fo_x86

Answer 1

考虑两个节点为A和B的二叉树。第一个树以B作为根节点，A为左子节点；第二个树以A作为根节点，B为右子节点。中序遍历匹配，但两个树不同。

- DrC

---

为了完整起见，这里举一个先序遍历不足的例子：树1是1-2-3，以2为根节点；树2是1-3，以1为根节点。 - Daniel Fischer

啊...我竟然想不出一个简单的例子。 - fo_x86

如果您添加标点并显示“null”指针，似乎可以只使用一个遍历，对吗？例如，如果您将每个节点表示为“null”或“(<value> <left> <right>)”，则您的第一棵树是“(B A null)”，第二棵树是“(A null B)”，因此没有歧义。 - Joshua Taylor

@JoshuaTaylor，那么您将会遇到3-3（左倾）和3-3（右倾）的问题。 - Cheng

@Cheng 这并不是这样的，因为有标点符号。树将会是（在**(value left right)表示法中）：(3 (3 null null) null)** 和 **(3 null (3 null null))**。没有歧义。 - Joshua Taylor

Answer 2

如果树不是二叉搜索树而是普通的二叉树，我认为你需要两者。任何一组节点都可以是前序遍历。假设有一个二叉树a、b、c、d、e、f、g、h，你的子树是cdef。你可以创建另一个具有子树cde和另一个子树fg的树。没有办法知道区别。

然而，如果它是二叉搜索树，你就不需要中序遍历。

顺便说一下，这里有一个有趣的算法问题：给定一个前序遍历，找到满足它的二叉树数量。

- user1952500

Answer 3

作为对user1952500答案的补充：如果它是一棵二叉搜索树，那么只有先序遍历或后序遍历可以使其唯一，而仅中序遍历则不行。例如：

  5
 / \
3   6

中序遍历：3-5-6 然而，另一棵二叉搜索树可以有相同的中序遍历：

3
 \
  5
   \
    6

此外，我认为 preorder+inorder+string_comparison 只适用于检查两棵树是否相同。它无法检查一棵树是否是另一棵树的子树。要查看示例，请参考 Determine if a binary tree is subtree of another binary tree using pre-order and in-order strings。

- user2356969

Answer 4

使用哨兵表示空节点的先序遍历已经足够好了。我们可以使用这种方法来序列化/反序列化二叉树。这意味着二叉树和它的带有哨兵的先序遍历表示之间存在一对一的映射关系。

- e230217