algorithm - 如何判断两棵二叉树的内容是否相同？

Question

我看到几篇关于如何确定两棵树的结构是否相同的帖子，但没有找到任何关于如何确定两棵树的内容是否相同的答案。

比如说，树节点定义如下。

TreeNode {
    string data;
    TreeNode* left;
    TreeNode* right
};

现在我有两棵二叉树，需要找出两棵树的内容是否相同。这两个在结构上可能不相同，我们也不能假设数据字符串在单词上是相同的。

例如，我们可能有以下两棵树。当我们按顺序行走时，这两棵树在内容上可以被视为相同。需要明确的是，当我们连接这两棵树中的所有节点字符串时，它们是相同的。即 abcdedfg

 (abc)
 |   \
 (d) (efg)

 (a)
 |  \
 (b) (cdefg)

我知道我们可以按顺序遍历来收集两棵树的所有字符串，我们可以比较生成的两个字符串，但我想知道是否有更有效的方法来比较两棵树，方法是通过某种方式遍历两棵树并行或创建迭代器。这些对我来说似乎都不是很明显，所以想获得一些反馈和一些代码片段以获得更好的想法。

提前致谢。

Answer 1

您可以使用逐字符比较的 DFS(深度优先搜索)遍历两棵树。这也将与双指算法相结合，在该算法中，您将根据要处理的元素以不同的速度遍历每棵树的节点。

以你的例子为例。树 1 和树，其中节点 X-Y 是行 X，元素 Y。树 1 节点 2-2 是“efg”:

Tree 1
(abc)
 |   \
 (d) (efg)

Tree 2
 (a)
 |  \
 (b) (cdefg)

算法将依次遍历每棵树的节点，逐个字符进行比较。

1. 从树 1 节点 1-1 开始
2. 从树 2 节点 1-1 开始
3. 比较a1和a2
4. 前进到树 2 节点 2-1
5. 比较b1和b2
6. 前进到树 2 节点 2-2
7. 比较c1和c2
8. 前进到树 1 节点 2-1
9. 比较d1和d2
10. 前进到树 1 节点 2-2
11. 比较e1和e2
12. 比较f1和f2
13. 比较g1和g2
14. 返回相同!