识别树是否是其他树的子树的算法

Question

我正在阅读破解编码面试,我对以下问题的解决方案有疑问:你有两个非常大的二叉树:T1,有数百万个节点,T2,有数百个节点.创建一个算法来确定T2是否是T1的子树.

它建议的简单解决方案是创建一个表示有序和预先顺序遍历的字符串,并检查T2的预订/有序遍历是否是T1的预订/有序遍历的子字符串.

我想知道为什么我们需要比较两个遍历？为什么不是两个遍历,为什么不是例如有序和后序.并且主要不仅仅是一次遍历就足够了吗？只说顺序或预订遍历？

Answer 1

一次穿越还不够。考虑图 1->2->3 和 2<-1->3。如果从节点 1 开始遍历，您会遇到顺序为 1、2、3 的节点。如果您只是创建一个显示前序的字符串，则两者会给出相同的结果：1,2,3

另一方面，如果您使用后序，那么两者将给出不同的结果。3,2,1和2,3,1

我敢打赌，对于任何一种排序，您都可以找到具有相同结果的两棵不同的树。

因此，对于您想要查看的任何其他对，您需要自己回答的问题是：是否有一棵树可以为两次遍历提供相同的顺序？我将把它留作思考，稍后再回来看看你是否明白了。