我正在阅读破解编码访问，并且对以下问题的解决方案有疑问： 您有两个非常大的二叉树：T1和数百万个节点，和T2，有数百个节点。创建一个算法来决定T2是否是T1的子树。确定树是否是其他树的子树的算法
它建议的简单方法是创建一个表示按顺序和预序遍历的字符串，并检查T2的预序/按序遍历是T1的预序/按序遍历的子字符串。
我在想，为什么我们需要比较两个遍历？为什么这两个遍历，为什么不例如按顺序和后序。主要不只是一次遍历就足够了？只说顺序或预先遍历？
一次遍历是不够的。考虑图1→2→3和2→3。如果从节点1开始并遍历，则会遇到1,2,3和1,2,3个节点。如果您只是创建显示预订的字符串，则两个节点会给出相同的结果：1,2,3
另一方如果你使用后期订单，那么这两者会给出不同的结果。 3,2,1和2,3,1
我敢打赌，任何一种排序，你可以找到两个不同的树，具有相同的结果。
所以你需要为自己回答你想要看的任何其他对的问题是：会不会有一棵树为这两个遍历提供相同的顺序？我将会留下这个想法，稍后再回来看看你是否有这个想法。
我觉得用sentinel代表空节点的遍历就足够了。我们可以使用这种方法来序列化/反序列化二叉树。这意味着，它是二叉树与其前序+标记表示之间的一对一映射。
之后我们得到了小树和大树的字符串。然后我们使用kmp算法进行字符串匹配。
我知道人们说我们必须同时使用预订和中间（或后序和中间）。但其中大多数只是遵循其他人的意见，而不是独立思考。
首先让我们来澄清你的意思是“子树”。标准的图形理论含义是“通过从树中删除零个或多个顶点和边而形成的子图，并且它本身就是一棵树” - 但是还有另一个常用的含义，即“删除边; 2个连接的组件保留，这两者都是子树“。前者的定义包括后者没有的一些树。 –
有趣的是，你给出的算法不适用于“子树”的一些合理的定义：作为一个数学家，我会打电话给一个4 <-2<-1-> 3-> 5的子树。但是第一个的前序不是第二个的子序列。 – Joel
当你说“二叉树”时，我们可以假设他们是“二叉搜索树”（即父母比其两个孩子中的任何一个都少）？另外，每个树中的节点上的值是否是唯一的，或者不是？ –